#T2067. 数组描述(Array Description)

数组描述(Array Description)

链接: https://cses.fi/problemset/task/1746

板块: Dynamic Programming

时限: 1.00 s | 内存: 512 MB

题目描述

你知道一个数组包含 nn 个介于 11 和 mm 之间的整数,并且相邻两个值的绝对差至多为 11。

给定一个数组的描述,其中某些值可能未知。你的任务是计算符合该描述的数组个数。

输入

第一行输入包含两个整数 nn 和 mm:数组大小和每个值的上界。

下一行包含 nn 个整数 x1,x2,…,xnx_1,x_2,\dots,x_n:数组的内容。值 00 表示未知值。

输出

输出一个整数:符合描述的数组个数对 109+710^9+7 取模的结果。

数据范围

1≤n≤1051 \le n \le 10^5 1≤m≤1001 \le m \le 100 0≤xi≤m0 \le x_i \le m

样例输入

3 5
2 0 2

样例输出

3

说明:满足条件的数组为 [2,1,2][2,1,2]、[2,2,2][2,2,2] 和 [2,3,2][2,3,2]。