Array Description

题目描述

你知道有一个长度为 n 的数组，数组中的整数在 1 到 m 之间，且相邻两个值的绝对差最多为 1。 给出该数组的描述，其中有些值可能未知，你的任务是计算符合描述的数组个数。

输入格式

第一行输入包含两个整数 n 和 m：数组大小以及每个值的上界。 下一行包含 n 个整数 $x_1,x_2,\dots,x_n$：数组的内容。值 0 表示该值未知。

输出格式

输出一个整数：符合描述的数组个数对 $10^9+7$ 取模。

3 5
2 0 2

3

提示

$1 \le n \le 10^5$ $1 \le m \le 100$ $0 \le x_i \le m$ 样例解释：数组 [2,1,2]、[2,2,2] 和 [2,3,2] 符合描述。

标签: CSES1746|动态规划|DP

来源

CSES1746|动态规划|DP