YJC plays automaton

YJC is an old driver of mini train, so he was the gold medal winner of "The fatter, the better" Contest held by socks mill sesame seed bun column. An automaton caught his eye during his trip to CTSC (Consume The Special Course).

The automaton has $n+1$ states, numbered from $0$ to $n$, while $0$ represents $NULL$. So he started his study out of curiosity:

He picked out a set of start states $S$ and found some rather interesting features:

There **exists** a string $str$, satisfying that after running $str$ on each element in set $S$ you will get some final states including $NULL$ and at least one state other than $NULL$. In other words, the number of the final states $NULL$ you will get should be in the range $[1,|S|-1]$. (At least one element will be $NULL$ and at least one element won't be $NULL$)

The sets meeting these requirements are called YJC sets.

Be aware that YJC set is not allowed to include $NULL$.

He wants to know how many YJC sets there are.


If automaton is a fresh word to you, you can try to understand it this way:

An automaton has $n+1$ states, numbered from $0$ to $n$, while $0$ represents $NULL$.The size of the alphabet of the automaton is $m$.

$\delta(i,j)(0\leq i \leq n,1\leq j\leq m)$, satisfying $0\leq \delta(i,j)\leq n$ and $\delta(0,j)=0$ is called a transition function.

Here is a program explaining how a string $str$ runs on a state $t$:

$for$ $i=0..str.length-1$
$t\leftarrow \delta(t,str[i])$

If you still cannot understand how automaton works, you can turn to

https://en.wikipedia.org/wiki/Automata_theory

for further information!

Multiple tests.

For each test:

The first line contains two integers $n,m(1\leq n\leq 888,1\leq m\leq 8)$, indicating the size of the automaton and the size of the alphabet.

The next n lines:

Each line lie $m$ elements, indicating transition function $\delta (i,j)$, the state $i$ transitions to $\delta (i,j)$ after reading the character $j$. Also, 0 represents $NULL$.
($1\leq i \leq n$ and $1\leq j \leq m$)

$NULL$ can only transitions to $NULL$.

There should be one and only one space between two integers, also, each line ends with an integer not a space. The file should end with one and only one line break.

In the final test, input file contains no more than 11000 lines. 31 groups of tests in total.

Because the final test consists of only one input file, there should be quite a lot small-range cases.

If your program can pass the largest single case within 0.5s (CPU 3.0 GHz), it shall pass the final test.

For each test:

One line an integer $ans$, indicating the number of YJC sets.
(modulo $998244353(7\times 17\times 2^{23}+1 $ a prime$))$

3 2
3 0
3 0
0 3

3

The possible YJC sets are $\{1,3\},\{2,3\},\{1,2,3\}$.

State $1$ is equivalent to $2$, so obviously ${1,2}$ is not a YJC set.

BestCoder Round #46