Hasan is organizing a chess competition, there 2^N participants, they are standing in a row and numbered from 1 to 2^N from left to right.

There are N rounds, in the each round player number 1 in current row play against player number 2 in current row and player number 3 in current row play against player number 4 in current row and so on, the winner of each game advances to the next round, so the number of participants in round i (1-based) is 2^N-i+1. all winners stand in a row in the next round in the same relative order as the current round.

the winner of last round is declared to be the winner of the competition.

Hasan has estimated the skills of the participants and now he know that if players i and j played against each other, then the probability that participant i win the game is A_i,j / 1000, of course A_j,i = 1000 - A_i,j, (for all i,j (i!=j) between 1 and 2^N), the result of any game will never be draw.

Now Hasan wants to know the chances of each participant to be the winner, Help Hasan to compute the probability that participant i will be the winner for each i between 1 and 2^N.

Let P_i be probability that i-th participant win, then find P_i * 1000^2N mod 10⁹+7 for all i between 1 and 2^N , it can be proven that P_i * 1000^2N is always integer.

Input:

First line contains integer N the next 2^N lines each contains 2^N integer numbers, the matrix A

Output:

print 2^N space-separated integers in a single line, the i-th integer is P_i * 1000^2N mod 10⁹+7

Constraints:

• 1 <= N <= 10
• 0 <= A_i,j <= 1000
• A_i,i = 0