P4489 [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$、每个人计划序列以及事件之间的相关关系。你需要计算一共有多少种本质不同的世界运行轨迹。

输入的第一行包括一个整数，表示人数 $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$ 类事件就是相关的，否则这两类事件不相关。

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

### 样例说明 样例中有 $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$ 的顺序，但是这两类事件是不相关的。 ### 数据规模 对于 $100\%$ 的数据，总人数 $N \leq 10$，事件种类数 $M \leq 15$，计划序列长度 $C_i \leq 20$，世界轨迹数 $T \leq 10^6$。