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$ です。