Hasan is organizing a chess competition, there 2N participants, they are standing in a row and numbered from 1 to 2N 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 2N-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 Ai,j / 1000, of course Aj,i = 1000 - Ai,j, (for all i,j (i!=j) between 1 and 2N), 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 2N.
Let Pi be probability that i-th participant win, then find Pi * 10002N mod 109+7 for all i between 1 and 2N , it can be proven that Pi * 10002N is always integer.
First line contains integer N the next 2N lines each contains 2N integer numbers, the matrix A
print 2N space-separated integers in a single line, the i-th integer is Pi * 10002N mod 109+7