Background

Eirin Yagokoro is a doctor living in Eientei. She has excellent medical skills and a lot of medical knowledge, so she can make all kinds of medicines.

Even so, Eirin often tests new medicines (including, but not limited to, experimenting on Reisen). However, Eirin has also started to use something called a "culture medium", to grow tiny youkai called "bacteria" as experimental materials.

Bacteria split very quickly. Each time they split, the number of bacteria can double. More interestingly, the offspring bacteria are not necessarily the same as the parent. In other words, the offspring bacteria may mutate, providing Eirin with lots of materials for her medicine experiments. Of course, having too many bacteria is also a headache; if the culture medium is full of bacteria moving around everywhere, Eirin will have to take measures to destroy them.

Before starting a new culture, Eirin wants to do some research on the genes of the bacteria. Since Eirin is busy making medicine, this task is given to you.

Problem Description

To describe the problem more conveniently, we first give the following definitions:

• Subarray segment: We define that array $B$ is a subarray segment of array $A$ starting from position $P$ if and only if $|A| + P - 1 \le |B|$ and $B_1=A_P,B_2=A_{P+1},\dots,B_{|B|}=A_{P+{|B|}-1}$.
• Number of occurrences as a subarray segment: We define the number of occurrences of array $B$ in array $A$ as a subarray segment as follows: initially set the count to $0$. Enumerate each distinct $P$. If array $B$ is a subarray segment of array $A$ starting from position $P$, then add one to the count. The final value is the number of occurrences of array $B$ in array $A$ as a subarray segment.
• Gene array: Each bacterium has a "gene array". It is an integer array with values in $[1,k]$.
• Target array: A "target array" is an integer array with values in $[1,k]$. In this problem, we are given $m$ different "target arrays"; the $i$-th array is $g_i$.
• Target bacterium: For a bacterium, denote its "gene array" by $X$. For each target array $g_1, g_2, \dots, g_m$, we count its "number of occurrences as a subarray segment" in $X$, and sum these counts. If the sum is odd, then we call this bacterium a "target bacterium".
• Gene mutation: "Gene mutation" is a transformation applied to a bacterium. Given a $k \times k$ mutation probability matrix $p$. Let the bacterium's "gene array" be $X$. For each element $X_i$ in $X$, $X_i$ is replaced by $j$ ($1 \le j \le k$) with probability $p_{X_i,j}$. From this definition, it is clear that $\forall i \in [1,k], \sum_{i=j}^k p_{i,j}=1$.

The process of one experiment is as follows:

• First, put one specified bacterium into an empty culture dish.
• In each of the following minutes, every existing bacterium splits into two bacteria, and each new bacterium's "gene array" is exactly the same as the original bacterium. After splitting, each gene undergoes one "gene mutation".
• After $t$ minutes, count the number of "target bacteria" in the culture dish, and end the experiment.

Now you are given a length $n$ "gene array" $s$. For each prefix array of $s$, namely $s[1,1],s[1,2],\dots,s[1,n]$, suppose this array is the initial bacterium's "gene array" at the start of the experiment. Please compute the expected number of "target bacteria" at the end of the experiment, modulo $10^9+7$.

Input Format

• The first line contains four integers $n,m,k,t$.
• The second line contains $n$ integers describing the array $s$.
• Then follow $m$ lines. The first integer of each line is $|g_i|$, the length of the "target array" $g_i$. The next $|g_i|$ integers describe the "target array" $g_i$.
• Since the matrix $p$ is a real-valued matrix and is inconvenient to input, we use another way to input $p$. Specifically, next input $k$ lines, each containing $k$ integers describing a $k \times k$ matrix $p'$. Then we have

$$p_{i,j}=\frac{p'_{i,j}}{\sum_{l=1}^k p'_{i,l}}.$$

Output Format

• Output $n$ lines, each containing one integer. It represents, assuming $s[1,i]$ is the initial bacterium's "gene array", the expected number of "target bacteria" after the experiment ends, modulo $10^9+7$.

2 2 2 1
1 1
1 1
2 2 2
1 1
1 1

1
500000005

5 5 5 1
1 4 2 3 3
3 1 1 4
3 5 1 4
4 1 4 1 4
2 5 3
1 5
9 9 8 2 4
4 3 5 3 2
1 4 7 4 8
3 6 4 7 1
1 4 5 1 4

250000002
273809526
931547626
97163867
377852186

Hint

Sample Explanation

Sample #1

• When the prefix length is $1$, the initial bacterium's "gene array" is $\{1\}$. After one split, it becomes $\{1\}$ and $\{2\}$ with probability $\frac 1 2$ each. If it becomes $\{1\}$, it is a "target bacterium"; if it becomes $\{2\}$, it is not a "target bacterium". After one split there are $2$ bacteria in the dish, so the expected total number of "target bacteria" is $\frac 1 2\times 2=1$.
  
• When the prefix length is $2$, the initial bacterium's "gene array" is $\{1, 1\}$. After one split, the bacteria become $\{1, 1\}, \{1, 2\}, \{2, 1\}, \{2, 2\}$ with probability $\frac 1 4$ each. Among them, $\{2, 2\},\{1,2\},\{2,1\}$ are all "target bacteria", and $\{1,1\}$ is not a "target bacterium" (because the substring $\{1\}$ appears twice). That is, the expected total number of "target bacteria" after splitting is $\frac 3 4$. After one split there are $2$ bacteria. Therefore, the expected number of "target bacteria" in the end is $\frac 3 4\times 2=\frac 3 2$.
  

Constraints

This problem uses bundled testdata, and there is no single Subtask that contains the constraints and limits of all other Subtasks.

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|c|c|} \hline \textbf{Subtask} & \textbf{Score} &\bm{n\le} & \bm{m\le} &\bm{k\le}&\bm{t\le} & \bm {|g_i|\le} & \textbf{Special Property} \cr \hline 1 & 1 & 10^5 & 10^5 & 100 & 0 & 10^5 \cr \hline 2 & 14 & 5 & 5 & 5 & 1 & 5 \cr \hline 3 & 15 & 10^3 & 1 & 10^3 & 1 & 100 & \text{A} \cr \hline 4 & 30 & 5\times 10^4 & 5 & 10 & 1 & 50 & \text{B} \cr \hline 5 & 20 & 5\times 10^4 & 5 & 10 & 10^3 & 50 \cr \hline 6 & 20 & 10^3 & 10^4 & 10 & 10^3 & 10^4 & \text{C}\cr \hline \end{array}$$

• Special Property $\textbf{A}$: For $i=1,2,\dots,m$, it is guaranteed that all integers in $g_{i}$ are $1$.
• Special Property $\textbf{B}$: For $i=1,2,\dots, k$ and $j=1,2,\dots,k$, it is guaranteed that $p'_{i,j}=1$.
• Special Property $\textbf{C}$: It is guaranteed that $\sum_{i=1}^m |g_i|\le 10^4$.

For all testdata, it is guaranteed that $1\le n,m,\sum|g_i| \le 10^5$. $0\le t\le 10^3$, $0\le p'_{i,j} \le 10^9$. Also, no row sum of the $p'$ matrix is $0$ modulo $10^9+7$.

Translated by ChatGPT 5