#3659. Which Dreamed It

内存限制:512 MiB 时间限制:20 Sec

题目描述

有n个房间,每个房间有若干把钥匙能够打开特定房间的门。
你会做这么件事情:
最初你在房间1。
每当你到达一个房间,你可以选择该房间的一把钥匙,前往该钥匙对
应的房间,并将该钥匙丢到垃圾桶中。
你希望:最终回到房间1,且垃圾桶中有所有的钥匙。
求方案数。两组方案不同,当且仅当使用钥匙的顺序不同。注意,每
把钥匙都是不同的。

输入格式

 有多组数据。
对于每组数据第一行输入一个数n,表示房间数。
接下来n行依次描述每个房间:
首先一个数s,表示这个房间的钥匙数目,接下来s个数,分别描述每把
钥匙能够打开的房间的门。
输入以n-0结尾。

输出格式

对于每组数据,输出方案数,为了方便你的输出,请将答案对1000003取模。

样例

样例输入


			
1
0
2
1 1
1 2
0

样例输出


			
1
0

数据范围与提示

在第一组样例中,没有钥匙,则方案数为1。

在第二组样例中,你不可能使用第二个房间的钥匙,所以方案数为0。



 

 

房间数小于等于100,钥匙数小于等于200000。

数据组数也不是特别多。