To master the "Songhuo Tandou Lightning Whip," one must first master the three-dimensional Hunyuan power.

Master Ma is a high-dimensional Tai Chi martial arts master. Based on his experience teaching boxing in $k$-dimensional space, he points out that as a $k$-dimensional being, you have $n_1 + \dots + n_k$ acupuncture points on your body, where $n_j$ points come from the $j$-th dimension. To practice the $k$-dimensional stereoscopic Hunyuan power, you must first open up the meridians; that is, these $n_1 + \dots + n_k$ points must be connected pairwise through meridians. In other words, if we treat the acupuncture points as vertices and the meridians between them as edges, they must form a connected graph. It is known that for two points located in dimensions $i$ and $j$ respectively, there are $a_{i,j}$ ways to connect them. Note that acupuncture points within the same dimension can also be connected, but a point cannot be connected to itself.

Please calculate the number of ways you can open up the meridians. Since the number of ways can be very large, you only need to output the result modulo $998244353$.

Input

The first line contains a positive integer $k$, representing the dimension of the space you are in.

The next line contains $k$ positive integers, where the $j$-th integer represents $n_j$, the number of acupuncture points in the $j$-th dimension.

The next $k$ lines each contain $k$ integers, where the $j$-th number in the $i$-th line represents $a_{i,j}$. It is guaranteed that $a_{i,j} = a_{j,i}$.

Output

Output a single integer representing the number of ways to open up the meridians, modulo $998244353$.

Examples

Input 1

2
2 1
1 2
2 1

Output 1

12

Note 1

There are $2+1=3$ nodes in total. There is $1$ way to connect $(1,2)$, and $2$ ways each to connect $(1,3)$ and $(2,3)$.

If $(1,2)$ is connected, there are $(2+1)^2-1=8$ ways to connect the rest.

If $(1,2)$ is not connected, then $(1,3)$ and $(2,3)$ must both be connected, resulting in $2 \times 2 = 4$ ways.

There are $8+4=12$ ways in total.

Input 2

2
7 4
1 998244352
998244352 0

Output 2

188336

Constraints

Let $N=(n_1+1)\times \dots \times(n_k+1)$.

For $100\%$ of the data, it is guaranteed that $N\le 2.5\times 10^5, 0\le a_{i,j} < 998244353$.