#P3659. [模板题][best定理]Which Dreamed It

    ID: 2854 传统题 2000ms 512MiB 尝试: 362 已通过: 87 难度: 7 上传者: 标签>难度分类提高+/省选-图论欧拉回路BEST 定理组合数学Matrix-Tree 定理线性代数与代数高斯消元排列数计算数论模逆元快速幂CF2300

[模板题][best定理]Which Dreamed It

题目描述

有 nn 个房间。每个房间里有若干把钥匙,每把钥匙能打开某个房间的门。所有钥匙都彼此不同。

你从 11 号房间出发。每次从当前房间选择一把尚未使用的钥匙,前往它对应的房间,并丢弃这把钥匙。你的目标是用完所有钥匙后回到 11 号房间。

求满足条件的方案数。两个方案不同,当且仅当使用钥匙的顺序不同。若没有钥匙,留在 11 号房间算一种方案。

输入格式

输入包含多组数据,没有预先给出的数据组数。

每组数据先输入一行整数 nn,表示房间数。接下来 nn 行依次描述每个房间:每行先给出该房间的钥匙数 ss,再给出 ss 个整数,依次表示每把钥匙可以打开的房间编号。

当读到 n=0n=0 时,输入结束。该行不对应一组数据。

输出格式

对于每组数据,输出一行一个整数,表示方案数对 106+310^6+3 取模的结果。

样例

1
0
2
1 1
1 2
0
1
0

第一组没有钥匙。第二组无法使用存放在 22 号房间的钥匙。

数据范围

原题给出的范围为 1≤n≤1001\le n\le 100,每组钥匙总数不超过 2×1052\times 10^5。