/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
長さ M の正整数列が N 個与えられます。i 個目の正整数列は A_i=(A_{i,1},A_{i,2},\dots,A_{i,M}) です。
これら N 個の正整数列から 1 個ずつ要素を選ぶ方法は M^N 通りありますが、その全てに対する「選んだ要素に含まれる整数の種類数」の総和を 998244353 で割った余りを求めてください。
制約
- 1 \le N,M \le 500
- 1 \le A_{i,j} \le NM
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M
A_{1,1} A_{1,2} \dots A_{1,M}
A_{2,1} A_{2,2} \dots A_{2,M}
\vdots
A_{N,1} A_{N,2} \dots A_{N,M}
出力
答えを出力せよ。
入力例 1
2 2 1 3 2 3
出力例 1
7
例えば、A_{1,1},A_{2,1} を選んだ場合、選んだ要素に含まれる整数は 1,2 の 2 種類となります。
A_{1,2},A_{2,2} を選んだ場合のみ種類数が 1 となり、他の 3 通りでは種類数が 2 となるため答えは 7 です。
入力例 2
2 2 1 1 1 2
出力例 2
6
入力例 3
3 5 3 1 3 4 2 5 2 1 2 3 4 6 2 5 6
出力例 3
327
Score : 400 points
Problem Statement
You are given N sequences of positive integers, each of length M. The i-th sequence is A_i=(A_{i,1},A_{i,2},\dots,A_{i,M}).
There are M^N ways to choose one element from each of these N sequences. Find the sum, modulo 998244353, of "the number of distinct integers among the chosen elements" over all such ways.
Constraints
- 1 \le N,M \le 500
- 1 \le A_{i,j} \le NM
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M
A_{1,1} A_{1,2} \dots A_{1,M}
A_{2,1} A_{2,2} \dots A_{2,M}
\vdots
A_{N,1} A_{N,2} \dots A_{N,M}
Output
Output the answer.
Sample Input 1
2 2 1 3 2 3
Sample Output 1
7
For example, if A_{1,1} and A_{2,1} are chosen, there are two distinct integers among the chosen elements: 1 and 2.
The number of distinct integers is 1 only when A_{1,2} and A_{2,2} are chosen, and it is 2 in the other three cases, so the answer is 7.
Sample Input 2
2 2 1 1 1 2
Sample Output 2
6
Sample Input 3
3 5 3 1 3 4 2 5 2 1 2 3 4 6 2 5 6
Sample Output 3
327