Universal Good Sequences Value Sum

Given three integers n, m, k, a sequence a of length m with each element in the range \( [1,k] \), and an \( n \times (m+1) \) matrix \( c \) (with 0-indexed columns from 0 to m), we define a sequence b of length n with elements in \( [1,k] \) to be good if every possible sequence of length m (with values in \( [1,k] \)) appears as a subsequence in b.

For a good sequence \( b \), let \( f(i) \) (denoted as pre_i) be the length of the longest prefix of \( a = (a_1, a_2, \dots, a_m) \) that is a subsequence of \( (b_1, b_2, \dots, b_i) \). (If no prefix is a subsequence, we define \( f(i)=0 \)). The value of a good sequence \( b \) is defined as:

[ Value(b)=\prod_{i=1}^{n} c_{i, f(i)} ]

Your task is to compute the sum of the values of all good sequences \( b \) of length n, modulo \( 10^9+7 \). Note that, since \( b \) must be good, in particular it must contain as subsequences every possible \( m \)-length sequence over \( [1,k] \).

inputFormat

The first line contains three integers \( n \), \( m \), and \( k \). The second line contains \( m \) integers representing the sequence \( a \). Then follow \( n \) lines, each containing \( m+1 \) integers. The \( i\text{-th} \) of these lines gives the values \( c_{i,0}, c_{i,1}, \dots, c_{i,m} \).

Note: It is guaranteed that every good sequence \( b \) (which is a sequence of length \( n \) with elements in \( [1,k]\)) must have the property that every possible \( m \)-length sequence (with values in \( [1,k] \)) is a subsequence of \( b \).

outputFormat

Output a single integer, the sum of the values of all good sequences \( b \) of length \( n \), modulo \( 10^9+7 \).

sample

3 1 2
1
1 2
3 4
5 6

210