题目描述

有 $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&滑大稽