Oblivionis took one final look at home before departing, resolutely deciding to leave the past behind. She wished that the magic of time could reshape her now chaotic heartbeat into a healthy, harmonious rhythm once again. But before she could truly forget everything, a question lingered in her mind: What if the events of the past had unfolded in a different order? Would the outcome have been different, and would her understanding of it have changed as well?

Given an $n \times n$ matrix $A$ over $\mathbb{F}_{998244353}$, consider how many matrices $B$ commute with $A$, i.e., how many matrices satisfy $AB = BA$. It can be proven that there exists a positive integer $k$ such that the number of such matrices is $998244353^k$. Please determine the value of $k$.

Input

The first line of the input contains a single integer $n$ ($1 \le n \le 500$).

The next $n$ lines describe the matrix $A$. The $i$-th line of these lines contains $n$ integers $A_{ij}$ ($0 \le A_{ij} < 998244353$), indicating the matrix $A$.

Output

Output a single line with a single integer, indicating the answer, $k$.

Examples

Input 1

3
1 2 3
4 5 6
7 8 9

Output 1

3

Input 2

3
1 1 0
0 1 0
0 0 1

Output 2

5