Generator

You are given $n$ different integer sequences. Each sequence has the same length $L$, and also all integers in these sequences are from 1 to $m$ .

There is a random machine that generates a random number sequence.

It generates a random number from 1 to $m$ every second.
When all $n$ sequences are generated as a consecutive subsequence of the sequence the machine generated, the machine is stopped immediately.

Now your task is to calculate the expected stopping time.

There are multiple test cases.

The first line of the input contains an integer $T$, the number of test cases.

Each test case begins with 3 positive integers$n(1\leq n\leq 15),m(1\leq M\leq 100,L(1\leq L\leq 20000)$, which are described above.

The next line will contain m positive integers $a_1,a_2,\cdots ,a_m$, which describes probability distribution of the dice. This means, the machine will generate 1 with probability $\frac{a_1}{(a_1+a_2+\cdots +a_m)}$ , 2 with probability $\frac{a_2}{(a_1+a_2+\cdots +a_m)}$, and so on. The total sum of $a_i$ does not exceeds 1000000000.

Each of the next $n$ lines contains a sequence of length $L$.

The total sum of $n\times L$ over all test cases will not exceed 777777.

For each test case, please calculate the answer as an irreducible fraction $\frac{A}{B}$ and output ($A\times B^{-1}\ mod\ 1000000007$) in a single line. Here $B^{-1}$ is the multiplicative inverse of $B$ modulo 1000000007.

The input guarantees that $B$ and 1000000007 is relatively prime.

1
1 2 2
1 1
1 1

6

金策工业综合大学（DPRK）

2016 Multi-University Training Contest 9