Teacher Mai 有一个包含 $n$ 个节点和 $n$ 条边的有向图。这个图很特殊：每个节点的出度均为 $1$，且没有自环。

对于每个节点，Teacher Mai 写下了一个直接指向该节点的节点集合。

例如，如果图包含 4 条边：$\{1 \to 2, 2 \to 4, 3 \to 1, 4 \to 1\}$，那么每个节点的集合分别为 $\{3, 4\}, \{1\}, \emptyset, \{2\}$。

但 Teacher Mai 发现他忘记记录这些集合分别属于哪个节点了。

Teacher Mai 想要恢复它，但他发现存在许多具有相同节点集合的图。你需要计算有多少种不同的图具有与给定集合相同的节点集合。

结果可能非常大，请输出结果对 $(10^9 + 7)$ 取模后的值。

如果无解，答案应为 $0$。

输入格式

输入包含不超过 $80$ 组测试数据，以一行 $0$ 结束。

对于每组测试数据，第一行包含一个整数 $n$ ($1 \le n \le 1000$)。

接下来 $n$ 行表示每个节点的集合。每行首先是一个整数 $p$，表示集合的大小。随后是 $p$ 个整数，表示集合中节点的编号（从 $1$ 到 $n$）。

输出格式

对于每组测试数据，输出问题的答案——即符合条件的图的数量，对 $10^9 + 7$ 取模。

样例

输入 1

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

输出 1

38