This is a complex and intricate world.

One morning, you wake up late and miss breakfast. You ride your bicycle to the supermarket, but you find that the staff have already put up new price tags, and snack prices have risen by 50%. In a fit of anger, you go hungry for the whole morning...

Of course, things might not develop this way at all.

One morning, you wake up late, but you still haven't missed breakfast. You ride your bicycle to the supermarket, and it just so happens that the staff haven't put the new price tags on the snacks yet. So, you successfully buy some breakfast and ride off happily...

Perhaps you might wake up earlier, or perhaps the supermarket staff might be late.

Sometimes, people just complete tasks in a predetermined order, but there may be some events whose relative order of occurrence affects the development of the world.

For example, if the supermarket has only one watermelon, and you want to buy it, and I also want to buy it, then the order in which we buy the watermelon will directly affect who ends up getting it.

In such a complex world, analyzing its operating laws is a very important task, and it is also what you need to study.

Description

For simplicity, assume there are a total of $N$ people and $M$ different types of events.

Define a binary relation "related" between events: The "related" relation is a binary relation, meaning we can only define whether two types of events are related; Events of the same type are always related; * If event $x$ is related to event $y$, then event $y$ is also necessarily related to event $x$;

Let $Q_i = (Q_{i,0}, Q_{i,1}, \dots, Q_{i,C_i-1})$ represent the sequence of events that the $i$-th person plans to complete (called a plan sequence), where $C_i$ is the length of $Q_i$. Each event $Q_{i,j}$ in $Q_i$ is one of the $M$ types of events, and events of the same type can occur multiple times.

As time passes, each event in every plan sequence will occur exactly once; for simplicity, no two events will occur at the same instant.

To describe the order of event occurrences, define $P$ as a development trajectory of the world, where $P$ is an ordered sequence satisfying the following conditions: 1. For every person, each event $Q_{i,j}$ in their plan sequence appears exactly once in $P$; 2. For any two events $Q_{i,j_1}$ and $Q_{i,j_2}$ belonging to the same plan sequence ($1 \le j_1 < j_2 \le C_i$), $Q_{i,j_1}$ must occur before $Q_{i,j_2}$ (i.e., it is located earlier in $P$);

Two trajectories $P_1$ and $P_2$ are defined as essentially different if and only if there exist two related events $Q_{i,j}$ and $Q_{u,v}$ whose relative order of occurrence is different in $P_1$ and $P_2$. That is, if $Q_{i,j}$ occurs before $Q_{u,v}$ in $P_1$ and $Q_{i,j}$ occurs after $Q_{u,v}$ in $P_2$, then $P_1$ and $P_2$ are essentially different; if $Q_{i,j}$ occurs after $Q_{u,v}$ in $P_1$ and $Q_{i,j}$ occurs before $Q_{u,v}$ in $P_2$, then $P_1$ and $P_2$ are also essentially different.

Note: Being "essentially the same" is transitive, i.e., if $P_1$ is essentially the same as $P_2$ and $P_2$ is essentially the same as $P_3$, then $P_1$ and $P_3$ must also be essentially the same.

Task

Given $N$, $M$, each person's plan sequence, and the "related" relationship between event types, you need to calculate the total number of essentially different world development trajectories.

Input

The first line contains an integer $N$, representing the number of people. The second line contains an integer $M$, representing the number of event types. All event types are numbered from $0$ to $M-1$.

The plan sequences for each person are then given sequentially. For the $i$-th person: The first line contains an integer $C_i$, the length of the sequence. The second line contains $C_i$ integers, giving each event $Q_{i,j}$ in $Q_i$ in order.

Finally, $M$ lines are provided, each containing $M$ integers (either 0 or 1), representing the $M \times M$ matrix $dep$ that describes the "related" relationship. $dep(i, j)$ represents the integer in the $i$-th row (from top to bottom) and $j$-th column (from left to right) of the matrix. If the value of $dep(i, j)$ is 1, then event type $i$ and event type $j$ are related; otherwise, they are not related.

Output

A single integer representing the number of essentially different world trajectories $T$.

Examples

Input 1

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

Output 1

4

Note

In the example, there are 2 people and 3 types of events, with $C_1 = C_2 = 2$. $Q_{1,0} = 0, Q_{1,1} = 1, Q_{2,0} = 2, Q_{2,1} = 1$. There are 4 different trajectories: $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})$

Any other legal development trajectory is essentially the same as one of these four. For example, $P = (Q_{2,0}, Q_{1,0}, Q_{2,1}, Q_{1,1})$ is essentially the same as $P_3$, because the two trajectories only swapped the order of $Q_{1,0} = 0$ and $Q_{2,0} = 2$, but these two event types are not related.

Constraints

Total number of people $N \le 10$; Number of event types $M \le 15$; Plan sequence length $C_i \le 20$; Number of world trajectories $T \le 10^6$.