P12152 【MX-X11-T6】Hypnosis

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

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$.

- 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 a single integer: the sum of values of all good sequences modulo $10^9+7$.

## 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$. | Subtask | $n \le$ | $m \le$ | $k \le$ | Special Property | Points | |:---------:|:---------:|:---------:|:---------:|:-------------------:|:--------:| | 1 | 8 | 8 | 8 | None | 5 | | 2 | 400 | 400 | 400 | A | 10 | | 3 | 50 | 50 | 50 | None | 10 | | 4 | 400 | 30 | 8 | None | 15 | | 5 | 400 | 30 | 400 | None | 15 | | 6 | 400 | 400 | 400 | B | 15 | | 7 | 400 | 400 | 400 | None | 30 | - **Special Property A**: All $c_{i,j}$ are equal. - **Special Property B**: All $a_i$ are equal. Translated by DeepSeek R1