문제 태그

• 기여도 분해
• 여사건
• 모듈러 연산

한국어 문제 해석

양의 정수로 이루어진 수열이 N개 주어진다. 각 수열의 길이는 M이다. i번째 수열은 $A_i = (A_i,1, A_i,2, ..., A_i,M)$ 이다.

이 N개의 수열 각각에서 원소를 하나씩 고르는 방법은 $M^N$가지 있다. 이 모든 선택 방법에 대해, 선택된 원소들 중 서로 다른 정수의 개수를 더한 값을 998244353으로 나눈 나머지를 구한다.

제약

• N과 M은 각각 1 이상 500 이하이다.
• 모든 i, j에 대해 $A_i,j$는 1 이상 N M 이하이다.
• 입력으로 주어지는 값은 모두 정수다.

입력

입력은 표준 입력에서 다음 형식으로 주어진다.

N M
A_1,1 A_1,2 ... A_1,M
A_2,1 A_2,2 ... A_2,M
...
A_N,1 A_N,2 ... A_N,M

출력

답을 출력한다.

문제 요약

• 각 행에서 정확히 하나의 위치를 고른다.
• 고른 값들의 서로 다른 종류 수를 점수로 본다.