19512번 - Generator 다국어

문제

You are given $n$ different integer sequences. All sequences have the same length $L,ドル and all integers in these sequences are from 1ドル$ to $m$.

You also have a machine that generates a stream of random numbers. Initially, the stream is empty. Every second, the machine generates a random integer from 1ドル$ to $m,ドル inclusive, and appends it to the stream. Each random integer is generated independently with the same probability distribution which is given to you.

With probability 1ドル,ドル eventually, each of the $n$ given sequences appears as $L$ consecutive elements of the stream. The occurrences of different sequences may overlap. At the first moment when each of the $n$ given sequences appeared at least once, the machine stops immediately. Your task is to calculate the expected number of seconds after which the machine stops.

입력

There are one or more test cases. The first line of input contains an integer $T,ドル the number of test cases.

Each test case starts with a line containing three positive integers $n,ドル $m$ and $L$: the number of sequences given, the upper bound for the integers which may appear in the sequences and in the stream, and the length of each given sequence, respectively (1ドル \leq n \leq 15,ドル 1ドル \leq m \leq 100,ドル 1ドル \leq L \leq 5 \cdot 10^4$).

The next line contains $m$ positive integers $a_1, a_2, \ldots, a_m$ which describe the probability distribution the machine uses to generate the stream. The machine will generate 1ドル$ with probability $a_1 / s,ドル 2ドル$ with probability $a_2 / s$ and so on, where $s = a_1 + a_2 + \ldots + a_m$. It is guaranteed that $s \le 10^9$.

Each of the next $n$ lines contains an integer sequence of length $L$. All integers in these sequences are positive and do not exceed $m$. It is guaranteed that all $n$ given sequences are pairwise distinct.

The total sum of $n \cdot L$ over all test cases does not exceed 777ドル,777円$.

출력

For each test case, calculate the answer as an irreducible fraction $\frac{A}{B}$ and output the integer $(A \cdot B^{-1}) \bmod (10^{9} + 7)$ on a separate line. Here, $B^{-1}$ is the multiplicative inverse of $B$ modulo 10ドル^{9} + 7$.

It is guaranteed that for all given inputs, the integers $B$ and 10ドル^{9} + 7$ are relatively prime.

제한

힌트