Teacher Mai has a directed graph with n nodes and n edges. This graph is special: Out degree of each node is 1, and there is no self loop.
For every node Teacher Mai wrote down a set of nodes which directly links to this node.
For example, the graph contains 4 edges: {1->2,2->4,3->1,4->1}, the set of each node is {3,4},{1},{},{2}
But Teacher Mai found that he forgot writing which node the set belonged to.
Teacher Mai wanted to recover it, but he found there are many graphs with the same node sets.
You should count the number of different graphs have the same node sets as the given one.
The number can be very large, just output the number modulo 1000000007 (10^9+7).
If there is no solution, the answer is 0.
