생성기

$n$개의 서로 다른 정수 수열이 주어진다. 모든 수열의 길이는 $L$로 같고, 수열에 들어 있는 모든 정수는 1 이상 $m$ 이하이다.

기계는 난수를 생성하여 스트림에 붙이는 장치이다. 처음에 스트림은 비어 있다. 기계는 매초 1 이상 $m$ 이하의 정수 하나를 무작위로 생성해 스트림 뒤에 붙인다. 각 난수는 주어진 확률 분포에 따라 서로 독립적으로 생성된다.

확률 1로, 결국 주어진 $n$개의 수열이 각각 스트림에서 연속한 $L$개의 원소로 한 번 이상 나타난다. 서로 다른 수열의 등장 위치는 겹칠 수 있다. 주어진 $n$개의 수열이 모두 적어도 한 번씩 나타난 순간, 기계는 즉시 멈춘다. 기계가 멈출 때까지 걸린 초의 기댓값을 구하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 양의 정수 $n$, $m$, $L$이 주어진다. 각각 수열의 개수, 수열과 스트림에 나올 수 있는 정수의 상한, 각 수열의 길이이다 ($1 \le n \le 15$, $1 \le m \le 100$, $1 \le L \le 5 \cdot 10^4$).

다음 줄에는 기계가 사용하는 확률 분포를 나타내는 양의 정수 $a_1, a_2, \ldots, a_m$이 $m$개 주어진다. 기계는 확률 $a_1 / s$로 1을, 확률 $a_2 / s$로 2를 생성하며, 이런 식으로 이어진다. 여기서 $s = a_1 + a_2 + \ldots + a_m$이다. $s \le 10^9$임이 보장된다.

다음 $n$개의 줄에는 길이 $L$의 정수 수열이 각각 주어진다. 이 수열의 모든 정수는 양의 정수이며 $m$을 넘지 않는다. 주어진 $n$개의 수열은 모두 서로 다르다고 보장된다.

모든 테스트 케이스에 대해 $n \cdot L$의 총합은 $777\,777$을 넘지 않는다.

각 테스트 케이스에 대해 답을 기약분수 $\frac{A}{B}$로 구한 뒤, $(A \cdot B^{-1}) \bmod (10^{9} + 7)$의 값을 한 줄에 출력한다. 여기서 $B^{-1}$은 $10^{9} + 7$을 법으로 하는 $B$의 곱셈 역원이다.

모든 입력에 대해 $B$와 $10^{9} + 7$은 서로소임이 보장된다.