Problem Statement

You have a simple undirected graph. Each vertex in this graph has an integer interval written on it, and there are $C_{i,j}$ vertices with the interval $[i,j]$ ($1 \leq i \leq j \leq N$). There are no vertices with other intervals.

For any two vertices, there is an undirected edge between them if and only if the written intervals intersect. Here, an interval $[a,b]$ and an interval $[c,d]$ intersect if and only if $\max(a,c) \leq \min(b,d)$.

Find the number of spanning trees of this graph, modulo $998244353$. Here, all vertices are pairwise distinguishable.

Constraints

• $2 \leq N \leq 400$
• $1 \leq C_{i,j} \leq 10^4$
• All numbers in the input are integers.

Input

The input is given from Standard Input in the following format:

N
C_{1,1} C_{1,2} \cdots C_{1,N}
C_{2,2} \cdots C_{2,N}
\vdots
C_{N,N}

Output

Print the answer.