说明

给定 $n,m,k$，还有一个长为 $m$ 的值域在 $[1,k]$ 中的整数序列 $a$，再给定一个大小为 $n \times (m+1)$ 的矩阵 $c$。

定义一个整数序列是好的，当且仅当它的值域在 $[1,k]$ 中且所有值域在 $[1,k]$ 的长为 $m$ 的整数序列都是它的子序列。

定义一个好的整数序列 $b$ 的价值为 $\prod\limits_{i=1}^n c_{i,pre_i}$，其中 $pre_i$ 为 $a$ 的最长前缀长度使得 $a_{1 \sim pre_i}$ 是 $b_{1\sim i}$ 的一个子序列，若不存在则 $pre_i = 0$。

求所有长度为 $n$ 的好序列的价值和，答案对 $10^9+7$ 取模。

输入格式

第一行，三个正整数 $n,m,k$。

第二行，$m$ 个正整数 $a_1,\ldots,a_m$。

接下来 $n$ 行，每行 $m+1$ 个正整数 $c_{i,0},c_{i,1},\ldots,c_{i,m}$。

输出格式

一行一个整数，表示所有好序列的价值和模 $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

提示

【样例解释 #1】

满足要求的序列有 $1,2$ 和 $2,1$ 两种，价值分别为 $2\times 3=6$ 和 $3\times 3 = 9$，所以总和为 $6+9=15$。

【数据范围】

本题使用子任务捆绑。

对于所有测试数据，$1 \le n,m,k \le 400$，$1\le a_i\le k$，$1 \le c_{i,j} < 10^9+7$。

• 特殊性质 A：保证所有 $c_{i,j}$ 相等。
• 特殊性质 B：保证所有 $a_i$ 相等。