Little Cyan Fish ha una matrice $W$ di dimensione $n \times n$.

Per una sequenza di interi $a_1, a_2, \ldots, a_n$ con $1 \le a_i \le n$, sia $b_i$ il numero di interi distinti che compaiono il maggior numero di volte nel prefisso $a_1, a_2, \ldots, a_i$. Ad esempio, nel prefisso $1, 2, 1, 2, 3$, sia $1$ che $2$ compaiono due volte, quindi $b_5 = 2$.

Little Cyan Fish definisce il peso della sequenza come

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

Trova la somma dei pesi di tutte queste sequenze. Poiché la risposta può essere molto grande, stampala modulo $998\,244\,353$.

Input

La prima riga dell'input contiene un singolo intero $n$ ($1 \le n \le 100$), che indica la lunghezza delle sequenze e la dimensione della matrice.

Le successive $n$ righe descrivono la matrice $W$. La $i$-esima di queste righe contiene $n$ interi $w_{i,1}, w_{i,2}, \ldots, w_{i,n}$ ($0 \le w_{i,j} < 998\,244\,353$).

Output

Stampa una singola riga contenente un singolo intero, che indica la somma dei pesi di tutte queste sequenze modulo $998\,244\,353$.

Esempi

Input 1

1
7

Output 1

7

Input 2

2
1 2
3 4

Output 2

14

Input 3

3
1 1 1
3 1 1
0 0 1

Output 3

6

Nota

Nel primo caso di test di esempio, l'unica sequenza è $(1)$, e il suo peso è $7$.

Nel secondo caso di test di esempio, le sequenze $(1, 1)$ e $(2, 2)$ hanno ciascuna peso $3$, mentre $(1, 2)$ e $(2, 1)$ hanno ciascuna peso $4$. La somma è $3 + 3 + 4 + 4 = 14$.

Nel terzo caso di test di esempio, una sequenza ha peso diverso da zero solo se tutti e tre i valori sono diversi. Ci sono sei sequenze di questo tipo, ciascuna con peso $1$.