P12152 【MX-X11-T6】「蓬莱人形 Round 1」催眠术

原题链接：。 --- 「こんな時代に誂えた 見て呉れの脆弱性」 「本当の芝居で騙される 矢鱈と煩い心臓の鼓動」 「残機は疾うにないなっている；； 擦り減る耐久性」 「目の前の事象を躱しつつ，生きるので手一杯！ 誰か、助けてね(^^♪」

给定 $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$ 取模。

无

无

**【样例解释 #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$。 |子任务编号|$n\le$|$m \le$|$k \le$|特殊性质|分值| |:-:|:-:|:-:|:-:|:-:|:-:| |$1$|$8$|$8$|$8$|无|$5$| |$2$|$400$|$400$|$400$|A|$10$| |$3$|$50$|$50$|$50$|无|$10$| |$4$|$400$|$30$|$8$|无|$15$| |$5$|$400$|$30$|$400$|无|$15$| |$6$|$400$|$400$|$400$|B|$15$| |$7$|$400$|$400$|$400$|无|$30$| - 特殊性质 A：保证所有 $c_{i,j}$ 相等。 - 特殊性质 B：保证所有 $a_i$ 相等。