题目描述

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

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

输入格式

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

第二行包含 $n$ 个整数 $x_1, x_2, \ldots, x_n$，代表数组的元素值。值为 $0$ 表示未知的值。

输出格式

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

样例

3 5
2 0 2

3

提示

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

1. $[2, 1, 2]$
2. $[2, 2, 2]$
3. $[2, 3, 2]$

数据范围

• $1 \le n \le 10^5$
• $1 \le m \le 100$
• $0 \le x_i \le m$