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

板块: Dynamic Programming

时限: 1.00 s ｜ 内存: 512 MB

题目描述

你知道一个数组包含 $n$ 个介于 $1$ 和 $m$ 之间的整数，并且相邻两个值的绝对差至多为 $1$。

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

输入

第一行输入包含两个整数 $n$ 和 $m$：数组大小和每个值的上界。

下一行包含 $n$ 个整数 $x_1,x_2,\dots,x_n$：数组的内容。值 $0$ 表示未知值。

输出

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

数据范围

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

样例输入

3 5
2 0 2

样例输出

3

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