7861: BZOJ3861：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

提示

没有写明提示

题目来源

By 镇海中学