Gene Mutation and Target Bacteria

Consider an integer array called a gene array whose values lie in \( [1,k] \). Each bacterium has a gene array. We are also given \( m \) distinct target arrays \( g_1, g_2, \dots, g_m \), each with values in \( [1,k] \). For an array \( A \) and an integer \( P \), we say that an array \( B \) is a subsegment of \( A \) starting at position \( P \) if and only if \( P+|B|-1\le |A| \) and \( B_1 = A_P, B_2 = A_{P+1}, \dots, B_{|B|} = A_{P+|B|-1} \). The occurrence count of an array \( B \) as a subsegment of \( A \) is defined as the number of positions \( P \) such that \( B \) appears as a subsegment of \( A \) starting at \( P \).

A bacterium is called a target bacterium if, when we take its gene array \( X \) and for each target array \( g_i \) count its number of occurrences in \( X \) (as defined above), the sum of these counts is odd.

The bacteria undergo a mutation experiment as follows. Initially, a single bacterium is placed in a petri dish with a given gene array. Then, for each minute:

• Every existing bacterium divides into two bacteria, each inheriting an identical copy of the gene array of the parent bacterium.
• Immediately after division, every gene in every bacterium mutates independently. If a gene initially has value \( x \), then it mutates to the value \( j \) with probability \( p_{x,j} \) where \( p \) is a given \( k\times k \) matrix satisfying \( \sum_{j=1}^{k} p_{x,j}=1 \) for each \( x=1,2,\dots,k \). In other words, after one minute each gene has its distribution updated by the matrix \( p \).

After \( t \) minutes, the experiment ends and the number of target bacteria in the petri dish is counted. Note that the total number of bacteria at the end is \( 2^t \); however, due to gene mutations the gene arrays may change from the initial state.

In this problem, you are given an integer \( n \) and an initial gene array \( s \) of length \( n \). For each prefix \( s[1..i] \) \( (1\le i\le n) \) considered as the initial gene array of the bacterium used in an experiment, compute the expected number (modulo \( 10^9+7 \)) of target bacteria at the end of the experiment.

Note: In this problem, although the mutation process is described in full generality, the test cases are chosen such that the mutation probability matrix \( p \) is the identity matrix. Hence, in every experiment the gene array never changes during the experiment and remains equal to its initial state. Consequently, the expected number of target bacteria is either \( 2^t \) (if the initial gene array qualifies as a target bacterium) or \( 0 \) (otherwise).

An initial gene array \( X \) qualifies as giving rise to target bacteria if for each target array, you count its number of occurrences in \( X \) (as subsegments) and the total sum of these counts is odd. For instance, if \( X=[1,2,1,2] \) and the only target array is \( g=[1,2] \) then the occurrences are at positions 1 and 3 (a total of 2, which is even) so \( X \) would not be considered target.

inputFormat

The input consists of the following in order:

1. A line containing four space-separated integers \( n, m, k, t \) where \( 1\le n \le 10^3 \), \( 1\le m \le 10 \), \( 1\le k \le 10 \), and \( 0\le t \le 10^3 \).
2. A line containing \( n \) space-separated integers: \( s_1,s_2,\dots,s_n \) representing the initial gene array \( s \), where each \( s_i \) satisfies \( 1\le s_i\le k \).
3. For each \( i \) from \( 1 \) to \( m \), a line beginning with an integer \( \ell_i \) (the length of target array \( g_i \)), followed by \( \ell_i \) space-separated integers representing \( g_i \) (each between 1 and \( k \)).
4. Finally, \( k \) lines follow, each containing \( k \) space-separated integers. The \( j \)-th number in the \( i \)-th line is \( p_{i,j} \). In the test cases, \( p \) is the identity matrix (i.e. \( p_{i,j}=1 \) if \( i=j \) and 0 otherwise).

Note: Since the mutation matrix is the identity matrix in all test cases, the gene array remains unchanged during the experiment.

outputFormat

Output a single line containing \( n \) space-separated integers. The \( i \)-th integer should be the expected number of target bacteria (modulo \( 10^9+7 \)) at the end of the experiment when the initial gene array is the prefix \( s[1..i] \). Recall that if the gene array qualifies as a target bacterium then the answer is \( 2^t \) (modulo \( 10^9+7 \)); otherwise, it is 0.

sample

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

0 2 2 0 0