[CTSC2009] 纷繁世界

这是一个纷繁复杂的世界。 某一天清晨你起床很迟，没有吃上早饭。于是你骑着自行车去超市，但是你又发现商店的工作人员已经重新贴上了价格标签，零食价格都涨了50%。你一怒之下就这样饿了一个上午…… 当然，事情也许完全不会这样发展。 某一天清晨你起床比较迟，但还是没有吃上早饭。于是你骑着自行车去超市，恰好商店的工作人员还没有把涨价后的价格标签贴在零食上。于是你顺利的买了一些早餐然后逍遥而去…… 或许你会起得更早，也或许商店的工作人员会迟到。 有时候，人们只是按照预想的顺序去完成一些事情，不过可能有一些事件，它们发生时间的前后顺序会影响世界的发展。 比如，如果商店只有一个西瓜，你想买，我也想买，那么我们买西瓜的先后顺序就会直接影响到谁最后能够买到西瓜。 这样一个复杂的世界，分析它的运行规律是一件非常重要的工作，也是你所要研究的。

简单起见，假定总共有$N$个人以及$M$种不同类型事件。 定义事件之间的二元关系“相关”： - 相关关系是一个二元关系，就是说我们只能定义两种类型的事件间是否相关； - 同一种类型的事件之间一定是相关的； - 若事件$x$与事件$y$是相关的，那么事件$y$与事件$x$也一定是相关的； 令$Q_i = (Q_{i, 1}, Q_{i, 2}, \cdots, Q_{i, C_i})$表示第$i$个人计划完成的事件序列（称为计划序列），$C_i$表示$Q_i$的长度。$Q_i$中每个事件$Q_{i,j}$都是$M$种事件中的某一种，且同一种类型的事件可以发生多次。 随着时间的推移每个计划序列中的事件都会发生一次且恰好一次；为了简单起见，不会有任何两个事件发生在同一时刻。 为了描述事件的发生顺序，定义$P = (Q_{i_1, j_1}, Q_{i_2, j_2}, \cdots, Q_{i_l, j_l})$为世界的一条发展轨迹，$P$是满足如下条件的有序序列： 1. 对于每个人，计划序列中的每个事件$Q_{i,j}$都在$P$出现一次且恰好一次； 2. 对于属于同一个计划序列的两个事件$Q_{i,j_1}$和$Q_{i,j_2}$（$1 \leq j_1 < j_2 \leq C_i$），$Q_{i,j_1}$一定发生在$Q_{i,j_2}$之前（也就是在$P$中位于更靠前的位置）； 两条轨迹$P_1$和$P_2$被定义为本质不同的，当且仅当存在两个相关的事件$Q_{i,j}$和$Q_{u,v}$，他们在$P_1$和$P_2$中发生的先后顺序不同，也就是说，如果在$P_1$中$Q_{i,j}$发生在$Q_{u,v}$之前且在$P_2$中$Q_{i,j}$发生在$Q_{u,v}$之后，那么$P_1$和$P_2$就是本质不同的；如果在$P_1$中$Q_{i,j}$发生在$Q_{u,v}$之后且在$P_2$中$Q_{i,j}$发生在$Q_{u,v}$之前，那么$P_1$和$P_2$也是本质不同的； 注意：本质相同具有传递性，即若$P_1$与$P_2$本质相同且$P_2$与$P_3$本质相同，那么$P_1$与$P_3$一定也本质相同。 给定$N, M$、每个人计划序列以及事件之间的相关关系。你需要计算一共有多少种本质不同的世界运行轨迹。

输入文件*world.in*第一行包括一个整数，表示人数$N$。 输入文件第二行包括一个整数，表示事件种类数$M$，所有类型的事件按照$0$至$M - 1$编号。 接下来依次给出每个人的计划序列的描述，对于第$i$个人： 首先一行一个整数表示序列长度$C_i$。 第二行包含$C_i$个整数，依次给出$Q_i$中的每个事件$Q_{i,j}$。 最后$M$行输入一个$M$行$M$列的矩阵$dep$用来描述相关关系，每行包含$M$个整数，都是$0$或者$1$。$dep(i,j)$表示矩阵自上往下的第$i$行，自左往右的第$j$列所包含的整数。若$dep(i, j)$的值为$1$，那么第$i$类事件和第$j$类事件就是相关的，否则这两类事件不相关。

输出文件*world.out*只有一行，一个整数表示本质不同的世界轨迹数$T$。

2 
3 
2 
0 
1 
2 
2 
1 
1 1 0 
1 1 1 
0 1 1

4

**【样例说明】** 样例中有$2$个人与$3$类事件，$C_1 = C_2 = 2$。$Q_{1,0} = 0, Q_{1,1} = 1, Q_{2,0} = 2, Q_{2,1} = 1$。 一共有$4$中不同的发生轨迹： $P_1 = (Q_{1,0}, Q_{1,1}, Q_{2,0}, Q_{2,1})$ $P_2 = (Q_{1,0}, Q_{2,0}, Q_{1,1}, Q_{2,1})$ $P_3 = (Q_{1,0}, Q_{2,0}, Q_{2,1}, Q_{1,1})$ $P_4 = (Q_{2,0}, Q_{2,1}, Q_{1,0}, Q_{1,1})$ 对于其他任何合法的发展轨迹，都一定和这四条轨迹中的某一条本质相同。例如$P = (Q_{2,0}, Q_{1,0}, Q_{2,1}, Q_{1,1})$与$P_3$是本质相同的，因为两条轨迹只交换了$Q_{1,0} = 0$和$Q_{2,0} = 2$的顺序，但是这两类事件是不相关的。 **【数据规模】** 总人数$N \leq 10$; 事件种类数$M \leq 15$; 计划序列长度$C_i \leq 20$; 世界轨迹数$T \leq 10^6$。