Counting Essentially Different World Trajectories

There are N persons and M different types of events. A binary relation of "related" is defined among event types as follows:

• The relation is binary, i.e. for any two event types you can specify whether they are related or not.
• Any two events of the same type are always related.
• If event type a is related to event type b, then b is related to a.

Each person i has a plan sequence Q_i = (Q_i,1, Q_i,2, ..., Q_i,Ci) where every event Q_i,j is of one of the M types (and the same type may occur several times in one plan). Over time, each event in every plan will occur exactly once and no two events occur simultaneously. A world trajectory is an interleaving sequence P = (Q_i₁,j₁, Q_i₂,j₂, ..., Q_iₗ,jₗ) such that:

1. For every person, each event in his/her plan appears exactly once in P.
2. For any two events from the same person (say Q_i,j₁ and Q_i,j₂ with j₁ < j₂), Q_i,j₁ appears before Q_i,j₂ in P.

Two trajectories P₁ and P₂ are defined as essentially different if and only if there exists a pair of related events Q_i,j and Q_u,v that occur in different relative orders between P₁ and P₂. That is, if in P₁ Q_i,j occurs before Q_u,v but in P₂ it occurs after, then they are essentially different. (Note that this notion is transitive.)

Given N, M, each person's plan sequence, and the relatedness between event types, calculate the number of essentially different world trajectories.

Important details:

• Events in the same plan must keep their original order.
• Two events are considered related if either they are of the same type or their types are declared related. This relation is symmetric.
• Interleavings that differ only by the order of events that are not related are considered essentially the same.
• The answer is guaranteed to be an integer.

Hint: Notice that the given relation on event types (being symmetric and reflexive) defines a graph on event types. Two event types are indirectly related if they are in the same connected component. In any valid trajectory, the relative order among events coming from the same connected component is what distinguishes the trajectory essentially. In fact, if for a connected component, one gathers all occurrences (keeping the per-person order constraints) then the number of distinct orders is given by the multinomial coefficient:

[ \frac{(n_1+n_2+\cdots+n_k)!}{n_1!,n_2!\cdots n_k!} ]

where n_i is, for each person, the count of events from that connected component. The final answer is the product over all connected components.

inputFormat

The input is given as follows:

1. The first line contains two integers N and M.
2. The next N lines describe the plan sequence for each person. Each of these lines starts with an integer C_i (the number of events in the plan) followed by C_i integers representing the event types (each in the range 1 to M).
3. The next M lines form the relatedness matrix. Each line contains M integers (each either 0 or 1), where the j-th integer in the i-th line indicates whether event type i and event type j are related. It is guaranteed that the matrix is symmetric and the diagonal entries are 1.

You may assume that all numbers are separated by spaces and/or newlines.

outputFormat

Output a single integer representing the number of essentially different world trajectories.

sample

1 1
3 1 1 1
1

1