Little Cyan Fish는 $n \times n$ 행렬 $W$를 가지고 있습니다.

$1 \le a_i \le n$을 만족하는 정수 수열 $a_1, a_2, \ldots, a_n$에 대해, 접두사 $a_1, a_2, \ldots, a_i$에서 가장 많이 등장하는 서로 다른 정수의 개수를 $b_i$라고 합시다. 예를 들어, 접두사 $1, 2, 1, 2, 3$에서는 $1$과 $2$가 모두 두 번 등장하므로 $b_5 = 2$입니다.

Little Cyan Fish는 이 수열의 가중치를 다음과 같이 정의합니다.

$$\prod_{i=1}^n w_{i,b_i}.$$

이러한 모든 수열의 가중치의 합을 구하세요. 답이 매우 클 수 있으므로, $998\,244\,353$으로 나눈 나머지를 출력하세요.

입력

입력의 첫 번째 줄에는 수열의 길이와 행렬의 크기를 나타내는 하나의 정수 $n$ ($1 \le n \le 100$)이 주어집니다.

다음 $n$개의 줄에는 행렬 $W$가 설명됩니다. 이 중 $i$번째 줄에는 $n$개의 정수 $w_{i,1}, w_{i,2}, \ldots, w_{i,n}$ ($0 \le w_{i,j} < 998\,244\,353$)이 주어집니다.

출력

이러한 모든 수열의 가중치의 합을 $998\,244\,353$으로 나눈 나머지를 나타내는 하나의 정수를 한 줄에 출력하세요.

예제

입력 1

1
7

출력 1

7

입력 2

2
1 2
3 4

출력 2

14

입력 3

3
1 1 1
3 1 1
0 0 1

출력 3

6

참고

첫 번째 예제 테스트 케이스에서는 유일한 수열이 $(1)$이며, 그 가중치는 $7$입니다.

두 번째 예제 테스트 케이스에서는 수열 $(1, 1)$과 $(2, 2)$가 각각 가중치 $3$을 가지며, $(1, 2)$와 $(2, 1)$은 각각 가중치 $4$를 가집니다. 합은 $3 + 3 + 4 + 4 = 14$입니다.

세 번째 예제 테스트 케이스에서는 세 값이 모두 다를 때에만 수열의 가중치가 영이 아닙니다. 그러한 수열은 여섯 개가 있으며, 각각의 가중치는 $1$입니다.