#CS1746. 数组描述

数组描述

题目背景

翻译自 CSES-1746 题。

题目描述

你知道一个数组有 n 个整数，这些整数的值在 1 到 m 之间，并且相邻两个值的绝对差不超过 1。

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

输入格式

第一行包含两个整数 n 和 m，分别代表数组的大小和每个值的上限。

第二行包含 n 个整数 x1,x2,…,xnx_1,x_2,…,x_nx1​,x2​,…,xn​，代表数组的元素值。值为 0 表示未知的值。

输出格式

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

样例

3 5
2 0 2

3

样例1解释 数组的长度是 3，最大值为 5。给定数组的第 1 和第 3 个元素的值为 2，第二个元素是未知的（为 0）。符合条件的数组有 3 种可能：

• [2,1,2][2, 1, 2][2,1,2]

• [2,2,2][2, 2, 2][2,2,2]

• [2,3,2][2, 3, 2][2,3,2]

说明/提示

$1\le n \le 10^5$

$1 \leq m \leq 100$

0≤xi≤m0 \leq x_i \leq m 0≤xi​≤m。