You are give an graph with multiple edges and without loops. Each edge have one of 2 colors -- black or white.
For each i between 0 and \(n-1\), inclusive, find number of spanning trees with exactly i white edges and \(n - 1 - i\) black edges.
As answers can be large, print them modulo \(1,000,000,007\).
Input Format:
First line contain single integer n -- number of vertices in a graph.
Then two tables \(n \times n\) follows, separated by an empty line.
First table contains number of white edges between vertices, second black.
n
\(w_{11} \dots w_{1n}\)
\(\vdots\)
\(w_{n1} \dots w_{nn}\)
\(b_{11} \dots b_{1n}\)
\(\vdots\)
\(b_{n1} \dots b_{nn}\)
Output Format:
Output n space-separated numbers, i containing number of trees with i white and \(n - 1 - i\) black edges.
Constraints:
\(2 \leqslant n \leqslant 100\).
\(0 \leqslant w_{ij}, b_{ij} \leqslant 1,000,000,006\).
\( w_{ii} = b_{ii} = 0\).
\( w_{ij} = w_{ji}, b_{ij} = b_{ji} \).
.