题目描述

译自 ROI Regional 2025 Day1 T4. Поиск сокровищ

为了寻找矿物资源，科学家们研发了一种特殊的扫描仪。

我们将搜索区域表示为一个包含 $k$ 行 $n$ 列的表格。行的编号从上到下为 $1$ 到 $k$，列的编号从左到右为 $1$ 到 $n$。每个单元格中都可能存在矿物资源。

扫描仪的工作方式如下：它可以在第 $p$ 列启动，并返回扫描区域中含有矿物的单元格数量。扫描区域包括第 $p$ 列的所有单元格，第 $p-1$ 列的前 $k-1$ 个单元格，第 $p-2$ 列的前 $k-2$ 个单元格，依此类推。下图展示了当 $k = 3$，$n=5$ 时，不同 $p$ 值下的扫描区域。

现在，给定扫描仪在所有列上的返回值，我们用 $b_p$ 表示第 $p$ 列的扫描结果。如果对于某个表格，已经确定每个单元格是否含有矿物，并且根据该表格，扫描仪返回的结果与给定的 $b_p$ 相符，则称该表格为 合法的。例如，如果在上述示例中，扫描仪返回的结果是 $[2, 1, 2, 3, 2]$，那么以下就是一个合法的表格（含有矿物的单元格用黑色三角形表示）：

根据给定的扫描结果，确定合法表格的数量，并输出该数量对 $10^9 + 7$ 取模的结果。请注意，扫描仪可能存在故障，导致没有任何合法的表格，这种情况下应输出 $0$。

输入格式

第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 200$, $1 \le k \le 7$)，分别表示列数和行数。

第二行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$ ($0 \le b_i \le k^2$)，扫描仪在每一列的返回值。

输出格式

输出一个整数，表示合法表格的数量对 $10^9 + 7$ 取模的结果。

样例

输入

5 3
2 1 2 3 2

输出

24

数据范围与提示