#P11700. [ROIR 2025] 寻找宝藏

[ROIR 2025] 寻找宝藏

题目背景

翻译自 ROIR 2025 D1T4

题目描述

为了寻找有用的矿产资源,科学家们开发了一种特殊的扫描仪。

假设搜索区域是一个包含 kk 行和 nn 列的表格。行号从上到下编号为 11kk,列号从左到右编号为 11nn。每个单元格中可能含有矿产资源。

扫描仪的工作原理如下:它可以从第 pp 列启动,并返回扫描区域内包含矿产资源的单元格数。扫描区域包括第 pp 列的所有单元格、第 p1p-1 列的前 k1k-1 个单元格、第 p2p-2 列的前 k2k-2 个单元格,以此类推。下图展示了当 k=3k=3n=5n=5 时,所有可能的 pp 值的扫描区域。

现在,给定扫描仪返回的每个 pp 值的结果,记为 bpb_p,即在第 pp 列的扫描区域内,矿产资源的数量。如果一个表格的矿产资源分布能匹配扫描仪的返回值,则称这个表格是“合法的”。比如,若扫描仪返回值为 [2,1,2,3,2][2, 1, 2, 3, 2],则其中一个合法的表格可能如下所示(含有矿产的单元格用黑色三角形表示):

你需要根据给定的扫描结果,确定合法表格的数量,并输出其对 109+710^9 + 7 取模的结果。注意,扫描仪可能存在故障,导致没有任何合法的表格,这种情况下应输出 00

输入格式

第一行输入两个整数 n,kn, k,分别表示列数和行数(1n200,1k71 \leq n \leq 200, 1 \leq k \leq 7)。

第二行输入 nn 个整数 b1,b2,,bnb_1, b_2, \dots, b_n,表示扫描仪返回的每个列的矿产数量(0bik20 \leq b_i \leq k^2)。

输出格式

输出一个整数,表示正确表格的数量对 109+710^9 + 7 取模的结果。如果没有正确的表格,输出 00

5 3
2 1 2 3 2

24

提示

本题使用 Subtask 捆绑测试。数据中 Subtask 0 是样例。

子任务 分数 特殊性质
11 77 k2k \leq 2
22 99 k3k \leq 3
33 99 k4k \leq 4
44 2020 k5k \leq 5
55 1515 k6k \leq 6
66 1010 1nk251 \leq n \cdot k \leq 25
77 3030