Little Cyan Fish-те өлшемі $n \times n$ болатын $W$ матрицасы бар.

$1 \le a_i \le n$ шартын қанағаттандыратын $a_1, a_2, \ldots, a_n$ бүтін сандар тізбегі үшін, $b_i$ арқылы $a_1, a_2, \ldots, a_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$-ге тең.