Josh is trapped inside a mirror maze!

The maze consists of ~N~ small rooms connected by mirrored hallways, such that there is exactly one bidirectional mirrored hallway between any two rooms. This maze is weird - hallways are not flat and can tunnel underneath each other as to not intersect each other, and there is no exit!

The hallway connecting the ~i~-th and ~j~-th room is associated with a value ~d_{i, j}~, representing the dizziness of the mirrors in that hallway. When Josh passes through a hallway, his dizziness will become the bitwise OR of his previous dizziness and the dizziness of that hallway.

Initially, Josh begins with a dizziness of ~0~, and starts in an unknown room. He will traverse exactly ~L~ hallways. Unfortunately, Josh's poor memory and poor sense of orientation results in him being unable to differentiate between the hallways coming out from a room - he can't even remember the hallway he just came from! Therefore, for each of the ~L~ hallways that Josh traverses, he will pick a hallway uniformly at random out of the hallways connected to his current room, and then traverse that hallway.

For each possible starting room, help Josh find the expected value of his dizziness after traversing all ~L~ hallways.

Constraints

~2 \le N \le 50~

~1 \le L \le 10^9~

~0 \le d_{i, j} \le 10^9~

~d_{i, j} = d_{j, i}~

~d_{i, i} = 0~ for ~1 \le i \le N~. Note that there is no hallway connecting a room to itself, and that this value is included just for easier input processing.

Subtask 1 [20%]

~2 \le N \le 25~

~1 \le L \le 50~

~0 \le d_{i, j} \le 50~

Subtask 2 [60%]

~2 \le N \le 25~

Subtask 3 [20%]

No additional constraints.

Input Specification

The first line contains two space separated integers containing the values of ~N~ and ~L~.

The ~i~-th of the following ~N~ lines contains ~N~ space separated integers, ~d_{i, 1}, d_{i, 2}, \dots, d_{i, N}~.

Output Specification

Print a single line containing ~N~ space separated integers, with the ~i~-th integer representing the expected value of Josh's final dizziness if he was to start in the ~i~-th room. It can be shown that this expected value can be expressed in the form ~\frac{P}{Q}~, where ~P~ and ~Q~ are integers with no common divisor greater than ~1~. Instead of printing the expected value as a floating point number, print ~PQ^{-1} \bmod 10^9+7~, where ~Q^{-1}~ is an integer such that ~QQ^{-1} \equiv 1 \pmod{10^9+7}~.

Sample Input

3 2
0 2 4
2 0 5
4 5 0

Sample Output

500000008 500000008 500000009

Explanation

Consider the case where Josh starts in the ~1~-st room. There are four possible moves that Josh could make, with equal probability:

• Travel to the ~2~-nd room and then back to the ~1~-st room. Josh's final dizzyness is ~2 \mathbin| 2 = 2~.
• Travel to the ~2~-nd room and then to the ~3~-rd room. Josh's final dizzyness is ~2 \mathbin| 5 = 7~.
• Travel to the ~3~-rd room and then back to the ~1~-st room. Josh's final dizzyness is ~4 \mathbin| 4 = 4~.
• Travel to the ~3~-rd room and then to the ~2~-nd room. Josh's final dizzyness is ~4 \mathbin| 5 = 5~.

Here, ~|~ denotes the bitwise OR operator.

Therefore, the expected value of Josh's final dizziness is ~\frac{2+7+4+5}{4} = \frac{9}{2}~.

The answer for the first room is therefore ~9 \times 2^{-1} \equiv 9 \times 500\,000\,004 \equiv 500\,000\,008 \pmod{10^9+7}~.