版权声明

本题版权归 所有。

题目来源：https://www.luogu.com.cn/problem/T720710

题目在导入时有改动。

题目描述

对于正整数序列 $\{a_n\}$，定义其「直方图」为所有满足 $y \le a_x$ 的第一象限整点 $(x, y)$ 构成的点集，其「生成图」为在其「直方图」的点中给所有距离为 $1$ 的点对连上边后形成的无权无向图，其「自由度」为其「生成图」中能被至少一条 $(1, a_1)$ 和 $(n, a_n)$ 之间最短路途经的点的数量。

现有一个部分项缺失的正整数序列 $\{b_n\}$，你需要给每个缺失的项填入一个不大于 $V$ 的正整数，求所有可能得到的序列的「自由度」之和。

答案对 $\bm{10^9 + 7}$ 取模。

输入格式

第一行两个正整数 $n, V\ (1 \le n \le 1000, 1 \le V \le 10^9)$。

第二行一个 $n$ 个非负整数 $\{b_n\}\ (0 \le a_i \le V)$，其中 $b_i = 0$ 表示该项缺失。

输出格式

输出一行一个非负整数表示答案。

样例

3 2
2 0 1

9