Eric and Lucas are both training for the Olympic sailing regatta, but the venue has only one course. Neither of them is willing to compromise or take turns, so they have to practise in the same space. The danger is at the marks (the inflatable buoys sailors must round), where boats bunch up and can collide. Coach Hung wants them to meet as rarely as possible. Eric always launches from the same mark, while Lucas may start at any other mark, and you have been asked how often they should expect to meet in each case.

The course is laid out around ~n~ marks, numbered from ~1~ to ~n~. Wind and currents push sailors between these marks according to fixed patterns.

For every pair of marks ~i~ and ~j~, you are given an integer ~w_{i,j}~. At the end of each minute, a sailor currently at mark ~i~ moves to mark ~j~ with probability ~\dfrac{w_{i,j}}{100}~. Every row of these values sums to ~100~.

Eric and Lucas follow these probabilities independently. Eric always starts at mark ~1~. Lucas may start at any mark ~s~ except mark ~1~.

Whenever both of them occupy the same mark after a minute has passed, they are said to have met.

For every starting mark ~s~ of Lucas from ~2~ to ~n~, determine the expected number of times the two sailors meet during the next ~k~ minutes.

Because the answers may be fractional, output them modulo ~10^9+7~. If an expected value equals the rational number ~\dfrac{p}{q}~ in lowest terms, output ~p \cdot q^{-1} \pmod{10^9+7}~.

Input

The first line contains two integers ~n~ and ~k~ (~2 \le n \le 100~, ~1 \le k \le 10^{18}~).

The next ~n~ lines each contain ~n~ integers. The ~j~-th integer on the ~i~-th of these lines is ~w_{i,j}~ (~0 \le w_{i,j} \le 100~). For every row ~i~, ~\sum_{j=1}^{n} w_{i,j} = 100~.

Output

Output a single line containing ~n-1~ integers. The ~i~-th of these should be the required answer when Lucas starts at mark ~i+1~.

Example 1

Input

2 2
80 20
30 70

Output

20000001

Explanation

The expected value is ~\dfrac{43}{50}~.

Example 2

Input

4 5
40 10 20 30
0 50 50 0
25 25 25 25
10 20 30 40

Output

21336070 454089224 404025250