题目背景

「こんな時代に誂えた 見て呉れの脆弱性」

「本当の芝居で騙される 矢鱈と煩い心臓の鼓動」

「残機は疾うにないなっている；； 擦り減る耐久性」

「目の前の事象を躱しつつ，生きるので手一杯！ 誰か、助けてね(^^♪」

题目描述

给定 $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

样例 1 解释

满足要求的序列有 $1,2$ 和 $2,1$ 两种，价值分别为 $2\times 3=6$ 和 $3\times 3 = 9$，所以总和为 $6+9=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 \le n,m,k \le 400$，$1\le a_i\le k$，$1 \le c_{i,j} < 10^9+7$。

子任务编号	$n\le$	$m \le$	$k \le$	特殊性质	分值
$1$	$8$			无	$5$
$2$	$400$			A	$10$
$3$	$50$			无
$4$	$400$	$30$	$8$		$15$
$5$			$400$
$6$		$400$		B
$7$				无	$30$

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