Bobo has a directed graph with $n + m$ nodes, labeled $1, 2, \dots, (n + m)$. He also has an $n \times (n + m)$ matrix $P$.

• If he is at node $u$ ($1 \leq u \leq n$) at time $t$, the probability that he is at node $v$ at time $(t + 1)$ is $P_{u, v} / 10000$.
• If he is at node $u$ ($u > n$) at time $t$, the probability that he is at node $u$ at time $(t + 1)$ is $1$.

At time $0$, Bobo is at node $1$. Find the probabilities $p_1, p_2, \dots, p_m$ that he is at nodes $(n + 1), \dots, (n + m)$ respectively, as time approaches infinity.

Input

The input contains multiple test cases. Process until the end of the file.

Each test case starts with two integers $n$ and $m$.

The next $n$ lines each contain $n + m$ integers $P_{i, 1}, P_{i, 2}, \dots, P_{i, n + m}$.

• $n, m \geq 1$
• $n + m \leq 500$
• $1 \leq P_{i, j} \leq 10000$
• $P_{i, 1} + P_{i, 2} + \dots + P_{i, n + m} = 10000$
• There are at most $100$ test cases, and all but one satisfy $n + m \leq 50$.

Output

For each test case, output $m$ integers representing $p_1, p_2, \dots, p_m$. The format is as follows: if $p_i = \frac{P}{Q}$ (where $\mathrm{gcd}(P, Q) = 1$), output $P \cdot Q^{-1} \bmod (10^9+7)$.

Examples

Input 1

1 2
5000 2000 3000
2 1
1000 2000 7000
1000 2000 7000
2 2
1000 2000 3000 4000
1000 2000 3000 4000

Output 1

800000006 200000002
1
428571432 571428576

Note 1

For the first test case, $p_1 = \frac{2}{5}, p_2 = \frac{3}{5}$.