問題文

$N$ 桁のダイヤル錠があります。 各ダイヤルは $0, 1, \dots, 9$ のいずれかを表示することができます。
はじめ、錠はロックされていて、全てのダイヤルは $0$ を表示しています。
ダイヤル錠は $1 \le i \leq N$ 全てについて左から $i$ 桁目が $A_i$ である状態でツルを引くと解錠できます。 ここで $\max(A_1, A_2, \dots, A_N) \neq 0$ が保証されています。
Alice はダイヤル錠を解錠したいと考えていますが、暗証番号 $A_1, A_2, \dots, A_N$ がわかりません。
そこで Alice は以下の一連の操作を 最大 $T$ 回 試すことにしました。

• あらかじめ $K$ 個の戦略が与えられる。 $i$ 個目の戦略は非負整数列 $(R_{i,1}, R_{i,2}, \dots, R_{i,N})$ で表される。
• 操作時、Alice は $1$ 以上 $K$ 以下の整数 $i$ を一様ランダムに選ぶ。 そして、$j=1,2,\dots,N$ について $j$ 番目のダイヤルを $R_{i,j}$ 回順方向に回す。
  • 言い換えると、現在の $j$ 個目のダイヤルが表示する番号を $c_j$ とした時、 $j=1,2,\dots,N$ について $(c_j + R_{i,j}) \bmod 10$ が表示された状態にする。
• そして、Alice はツルを引きダイヤル錠が解錠できるか試す。 解錠に成功した場合、以降は操作を行わない。

制約

• $1 \leq N \leq 5$
• $1 \leq K \leq 10^N - 1$
• $1 \leq T \leq 10^9$
• $0 \leq A_i \leq 9$
• $\max(A_1, A_2, \dots, A_N) \neq 0$
• $0 \leq R_{i,j} \leq 9$
• $\max(R_{i,1},R_{i,2},\dots,R_{i,N}) \neq 0$
• $i \neq j$ ならば $(R_{i,1},R_{i,2},\dots,R_{i,N}) \neq (R_{j,1},R_{j,2},\dots,R_{j,N})$
• 入力される値は全て整数

入力

$N$ $K$ $T$
$A_1$ $A_2$ $\dots$ $A_N$
$R_{1,1}$ $R_{1,2}$ $\dots$ $R_{1,N}$
$R_{2,1}$ $R_{2,2}$ $\dots$ $R_{2,N}$
$\vdots$
$R_{K,1}$ $R_{K,2}$ $\dots$ $R_{K,N}$

出力

Alice が解錠に成功する確率を $\text{mod }120586241$ で計算した答えを出力して、最後に改行してください。

サンプル

2 3 2
1 2
1 2
3 4
8 8

26796943

4 1 2
2 4 6 8
1 2 3 4

1

5 10 1000000000
5 9 3 0 4
8 7 5 4 0
5 7 7 8 4
5 6 3 6 1
7 1 5 6 2
7 5 4 0 8
7 9 0 1 5
6 8 3 5 3
0 2 4 6 4
6 4 6 3 2
7 1 4 5 4

78122554