You are given a directed graph with n vertices and m edges. The vertices are numbered from 1 to n.
For each vertex ii, find out the number of ways to choose exactly n-1 edges to form a tree, where all the other n-1 vertices can be reached from i through these n-1 edges.
For each test case, output n integers in a line, the i-th integer denotes the answer for vertex ii. Since the answer may be too large, print it after modulo 109+7.
Please do not have any space at the end of the line.
2
1 0
7 12
1 3
2 1
1 4
5 1
4 7
6 5
2 3
4 6
3 1
6 4
7 1
1 21
2 3 1 4 2 6 2