And I need not search the idle courtyard alone To meet the youth who will listen to my lute for the rest of my life

Given an undirected simple graph $G$ with $n$ vertices, we replicate it $k$ times to obtain an undirected graph with $kn$ vertices and $km$ edges. Let $f_k$ be the number of matchings in its complement graph. Note that the matchings here do not necessarily have to be perfect matchings.

For each $k = 1, \dots, l$, calculate $f_k \pmod{998244353}$.

Input

The first line contains two positive integers $n$ and $l$.

The next $n$ lines contain an $n \times n$ $01$ matrix, where $G_{i,j} = G_{j,i}$ and $G_{i,i} = 0$. $G_{i,j} = 1$ indicates that there is an edge between vertex $i$ and vertex $j$.

Output

Output $l$ lines, each containing one integer. The $k$-th line should output $f_k \pmod{998244353}$.

Constraints

For $100\%$ of the data, $1 \le l \le 3 \times 10^5$ and $1 \le n \le 40$.

There are $20$ test cases in total, generated using a Cartesian product: $$(n, l) \in \{20, 30, 36, 40\} \times \{1, 10^2, 10^4, 10^5, 3 \times 10^5\}$$

The corresponding $(n_i, l_j)$ data will be scored as $a_i \cdot b_j$, where: $$a = [4, 3, 2, 1], b = [3, 3, 2, 1, 1]$$

Examples

Input 1

4 5
0 1 1 1
1 0 0 1
1 0 0 0
1 1 0 0

Output 1

3
321
58963
19412193
957504186