【模板】BEST 定理 | Which Dreamed It

有 $n$ 个房间，每个房间有若干把钥匙能够打开特定房间的门。 最初你在房间 $1$。每当你到达一个房间，你可以选择该房间的一把钥匙，前往该钥匙对应的房间，并将该钥匙丢到垃圾桶中。 你希望最终回到房间 $1$，且垃圾桶中有所有的钥匙。 你需要求出方案数，答案对 $10^6 + 3$ 取模。两组方案不同，当且仅当使用钥匙的顺序不同。 注意，每把钥匙都是不同的。 原 BZOJ3659。

**本题有多组数据。** 第一行一个整数 $T$，表示数据组数。 对于每组数据： 第一行一个整数 $n$。 接下来 $n$ 行，第 $i$ 行描述房间 $i$： 首先一个数 $s$，表示这个房间的钥匙数目，接下来 $s$ 个数，分别描述每把钥匙能够打开的房间的门。

对于每组数据，一行一个整数，表示答案对 $10^6+3$ 取模后的值。

2
1
0
2
1 1
1 2

1
0

【样例说明】 在第一组样例中，没有钥匙，则方案数为 $1$。 在第二组样例中，你不可能使用第二个房间的钥匙，所以方案数为 $0$。 【数据范围】 对于 $50\%$ 的数据，$n \le 4$，$\sum s \le 30$。 对于 $100\%$ 的数据，$1 \le T \le 15$，$1 \le n \le 100$，$0 \le \sum s \le 2 \times 10^5$。 2021/5/14 加强 by [SSerxhs](https://www.luogu.com.cn/user/29826)&[滑大稽](https://www.luogu.com.cn/user/203743)