Given a directed graph with $n$ nodes that is regular and strongly connected, and contains no self-loops or multiple edges between the same pair of nodes.
A snake of length $m$ lives on the graph, consisting of $m+1$ nodes (the "joints") and $m$ edges (the "body"). Specifically, a "state" of the snake is defined by a sequence of nodes $a_0, a_1, \dots, a_m$ ($1 \le a_i \le n$), where the snake's head is at node $a_0$ and the tail is at node $a_m$. For each $i$ ($1 \le i \le m$), the $i$-th segment of the body is a directed edge from $a_i$ to $a_{i-1}$. Multiple joints can occupy the same node, and multiple segments of the body can occupy the same edge. Two states are different if and only if their sequences of nodes are different.
A "move" allows the snake to transition from state $a_0, a_1, \dots, a_m$ to $b_0, b_1, \dots, b_m$ if and only if $b_i = a_{i-1}$ for all $1 \le i \le m$, and there exists a directed edge from $a_0$ to $b_0$. In other words, the snake crawls to an adjacent node by moving its head.
Starting from any state, find the number of ways to visit all distinct states exactly once. Output the answer modulo $998\,244\,353$. Two paths are considered different if their starting states are different or if the sequence of states visited is different.
Recall: A directed graph is regular if the in-degree and out-degree of every node are equal to a fixed value. A directed graph is strongly connected if there is a path between any two nodes.
Input
The first line contains two integers $n$ and $m$ ($2 \le n \le 500$, $1 \le m \le 10^9$), representing the number of nodes and the length of the snake.
The next $n$ lines each contain $n$ integers $e_{i,1}, e_{i,2}, \dots, e_{i,n}$ ($e_{i,j} \in \{0, 1\}$), where $e_{i,j} = 0$ indicates there is no directed edge from node $i$ to node $j$, and $e_{i,j} = 1$ indicates there is a directed edge from node $i$ to node $j$.
It is guaranteed that the graph is regular and strongly connected, and contains no self-loops, i.e., $e_{i,i} = 0$ ($1 \le i \le n$).
Output
Output a single integer, the number of valid paths modulo $998\,244\,353$.
Examples
Input 1
4 2 0 1 1 0 1 0 0 1 0 1 0 1 1 0 1 0
Output 1
640
Input 2
6 5 0 0 0 1 1 1 1 0 1 1 0 0 0 1 0 0 1 1 1 1 0 0 1 0 0 1 1 0 0 1 1 0 1 1 0 0
Output 2
495839213
Note
In the first example, one possible valid path is shown below:
