Tree

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.

There are multiple test cases, terminated by a line "0".

For each test case, the first line contains a integer n (1<=n<=1000).

The following are n lines representing the set of each node. For every line, there is a integer p first, indicating the size of the set. Then there are p integers, indicating the node with index from 1 to n in this set.

For each test case, output one line "Case #k: ans", where k is the case number, counting from 1, ans is the number module 10^9+7.

6
1 1
0
0
0
2 2 3
3 4 5 6
0

Case #1: 38

xudyh

2014 Multi-University Training Contest 8