Description

Given $n, m, k$, a length-$m$ integer sequence $a$ with values in $[1, k]$, and an $n \times (m+1)$ matrix $c$.

An integer sequence is defined as good if and only if:

1. All its values are in $[1, k]$.
2. Every length-$m$ integer sequence with values in $[1, k]$ is a subsequence of it.

For a good sequence $b$ of length $n$, its value is defined as $\prod\limits_{i=1}^n c_{i, \text{pre}_i}$, where $\text{pre}_i$ is the maximum prefix length of $a$ such that $a_{1 \sim \text{pre}_i}$ is a subsequence of $b_{1 \sim i}$. If no such prefix exists, $\text{pre}_i = 0$.

Find the sum of values of all length-$n$ good sequences, modulo $10^9+7$.

Input Format

• The first line contains three positive integers $n, m, k$.
• The second line contains $m$ positive integers $a_1, \ldots, a_m$.
• The next $n$ lines each contain $m+1$ positive integers $c_{i,0}, c_{i,1}, \ldots, c_{i,m}$.

Output Format

Output a single integer: the sum of values of all good sequences modulo $10^9+7$.

2 1 2
2
2 3
2 3

15

10 2 5
2 3
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1

14400

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

350920080

Hint

Explanation #1

The valid good sequences are $(1, 2)$ and $(2, 1)$. Their values are $2 \times 3 = 6$ and $3 \times 3 = 9$, respectively. The total sum is $6 + 9 = 15$.

Constraints

This problem uses subtask scoring.

For all test data: $1 \le n, m, k \le 400$, $1 \le a_i \le k$, $1 \le c_{i,j} < 10^9+7$.

• Special Property A: All $c_{i,j}$ are equal.
• Special Property B: All $a_i$ are equal.

Translated by DeepSeek R1