Given an $N \times N$ matrix $A_{ij}$, calculate its determinant $\det A$ modulo $998\,244\,353$.

Input

The first line of the input contains an integer $N$.

The next $N$ lines each contain $N$ integers. The $j$-th integer in the $i$-th line represents $A_{ij}$.

Output

Output a single integer representing the answer.

Examples

Input 1

3
1 1 4
5 1 4
19 19 810

Output 1

998241417

Subtasks

For all test cases, $1 \leq N \leq 500$ and $0 \leq A_{ij} < 998\,244\,353$.