「Wdsr-3」蓬莱药局

八意永琳是居住在永远亭的医生。她有着精湛的医术以及大量的医学知识，因而可以制造出各种的药物。 尽管如此，八意永琳常常为新的药物进行试验（包括但不限于对铃仙下手）。不过，八意永琳也开始使用被称为「培养基」一类的东西，培养被称为「细菌」的微小妖怪作为实验材料了。 细菌的分裂能力很强。每一次分裂，细菌的数目都能翻倍。更有意思的是，产生的细菌的子代不一定与亲代相同。换言之，子代细菌会发生变异，从而为永琳的药物实验提供了大量的材料。当然了，细菌太多也是一件苦恼的事情；如果培养基里长满了四处活跃的细菌，那么永琳将不得不采取措施，消灭它们。 在执行一次新的培养之前，永琳希望对细菌上的基因进行一些研究；由于永琳忙着去制药，因此这个任务就交给你了。

为了更方便地描述题意，我们先给出以下定义： - **子段**：我们定义数组 $B$ 是数组 $A$ 从 $P$ 位置开始的子段，当且仅当 $|A| + P - 1 \le |B|$ 且 $B_1=A_P,B_2=A_{P+1},\dots,B_{|B|}=A_{P+{|B|}-1}$． - **作为子段的出现次数**：我们定义数组 $B$ 在数组 $A$ 中作为子段的出现次数为：初始设次数为 $0$．枚举每个不同的 $P$，若数组 $B$ 是数组 $A$ 从 $P$ 位置开始的子段，则将次数加一．最后得到的值即为数组 $B$ 在数组 $A$ 中作为子段的出现次数． - **基因数组**：每个细菌都有一个「基因数组」．它是一个值域为 $[1,k]$ 的整数数组． - **目标数组**：「目标数组」是一个值域为 $[1,k]$ 的整数数组．在本题中，我们会给定 $m$ 个不同的「目标数组」，第 $i$ 个数组为 $g_i$． - **目标细菌**：对于一个细菌，记它的「基因数组」为 $X$．我们统计每个「目标数组」$g_1, g_2, \dots, g_m$ 分别在 $X$ 中「作为子段的出现次数」，并将它们求和．若得到的和为 **奇数**，则我们称这个细菌为一个「目标细菌」． - **基因突变**：「基因突变」是作用于一个细菌的变换．给定一个 $k \times k$ 的突变概率矩阵 $p$．记这个细菌的「基因数组」为 $X$．对于 $x$ 中的每个元素 $X_i$，$X_i$ 会以 $p_{X_i,j}$ 的概率替换为 $j$（$1 \le j \le k$）．根据此定义，显然有 $\forall i \in [1,k], \sum_{i=j}^k p_{i,j}=1$． 一次实验的过程如下： - 首先在一个空的培养皿中放入一个指定的细菌． - 在接下来的每分钟，现有的每个细菌会分裂成两个细菌，每个细菌的「基因数组」与原细菌完全相同．分裂之后，每个基因都会进行一次「基因突变」． - $t$ 分钟后，统计培养皿中「目标细菌」的数量，并结束实验． 现在给定一个长度为 $n$ 的「基因数组」$s$．对于 $s$ 的每个前缀数组 $s[1,1],s[1,2],\dots,s[1,n]$，假设该数组是实验开始时放入的细菌的「基因数组」，请你求出实验结束时得到的「目标细菌」的数量的期望，对 $10^9+7$ 取模．

- 第一行输入四个整数，$n,m,k,t$． - 第二行输入 $n$ 个整数，描述数组 $s$． - 接下来输入 $m$ 行．每行第一个整数 $|g_i|$ 表示「目标数组」$g_i$ 的长度．接下来 $|g_i|$ 个整数描述「目标数组」$g_i$． - 由于 $p$ 矩阵为实数矩阵，输入不方便，因此我们采用另一种方式输入 $p$ 矩阵．具体而言，接下来输入 $k$ 行，每行包含 $k$ 个整数，描述一个 $k \times k$ 的矩阵 $p'$．则有 $$ p_{i,j}=\frac{p'_{i,j}}{\sum_{l=1}^k p'_{i,l}}. $$

- 输出 $n$ 行，每行一个整数．表示假设以 $s[1,i]$ 为初始细菌的「基因数组」，实验结束后能得到的「目标细菌」的数量的期望，对 $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

### 样例解释 #### 样例 \#1 - 当前缀长度为 $1$ 时，初始细菌的「基因数组」为 $\{1\}$．分裂一次后变为 $\{1\}$ 和 $\{2\}$ 的概率均为 $\frac 1 2$．若变为 $\{1\}$，则是「目标细菌」；若变为 $\{2\}$，则不是「目标细菌」．分裂一次后培养皿中有 $2$ 个细菌，故「目标细菌」总数的期望为 $\frac 1 2\times 2=1$．  - 当前缀长度为 $2$ 时，初始细菌的「基因数组」为 $\{1, 1\}$．分裂一次后的细菌变为 $\{1, 1\}, \{1, 2\}, \{2, 1\}, \{2, 2\}$ 的概率都为 $\frac 1 4$．其中 $\{2, 2\},\{1,2\},\{2,1\}$ 均为「目标细菌」，$\{1,1\}$ 不是「目标细菌」（因为出现了两次子串 $\{1\}$）．即分裂后的「目标细菌」的总数的期望为 $\frac 3 4$．分裂一次后培养皿中有 $2$ 个细菌．即最后「目标细菌」数量之和的期望为 $\frac 3 4\times 2=\frac 3 2$．  ### 数据范围 **本题采用捆绑测试，且不存在一个 Subtask 包含其他所有 Subtask 的数据范围和限制．** $$ \def{\arraystretch}{1.5} \begin{array}{|c|c|c|c|c|c|c|c|} \hline \textbf{Subtask} & \textbf{分值} &\bm{n\le} & \bm{m\le} &\bm{k\le}&\bm{t\le} & \bm {|g_i|\le} & \textbf{特殊性质} \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} $$ - **特殊性质** $\textbf{A}$：对于 $i=1,2,\dots,m$，保证 $g_{i}$ 中所有整数均为 $1$ - **特殊性质** $\textbf{B}$：对于 $i=1,2,\dots, k$，$j=1,2,\dots,k$，保证 $p'_{i,j}=1$ - **特殊性质** $\textbf{C}$：保证 $\sum_{i=1}^m |g_i|\le 10^4$ 对于所有数据，保证 $1\le n,m,\sum|g_i| \le 10^5$．$0\le t\le 10^3$，$0\le p'_{i,j} \le 10^9$．且 $p'$ 矩阵不会出现某一行的和在模 $10^9+7$ 意义下为 $0$．