[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$。

样例 #1

样例输入 #1

2 
3 
2 
0 
1 
2 
2 
1 
1 1 0 
1 1 1 
0 1 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$。