题目描述

peter 有一个整数序列 \(a_1\), \(a_2\), …, \(a_n\)，他想让序列中所有的数都变成 h。他可以执行以下操作：选择一个区间 \([l, r]\)，让区间内的所有数增加 1。多次选择不同区间可以让整个序列都变成 h。不过在选择区间时，任何区间的左端点不能一样，右端点也不能一样。
问你有多少种方案能让序列中的 n 个元素都变成 h。由于方案数比较多，输出方案数对 1000000007 (\(10^9 + 7\))取模的结果。

输入格式

第一行两个整数 n, h；
接下来 n 个整数 \(a_1\), \(a_2\), …, \(a_n\)。

输出格式

输出方案数取模的结果。

样例1

输入

3 2
1 1 1

输出

4

样例2

输入

5 1
1 1 1 1 1

输出

1

样例3

输入

4 3
3 2 1 1 1

输出

0

数据范围

对于 30%的数据，1 \(\leq\) n, h \(\leq\) 100，0 \(\leq\) \(a_i\) \(\leq\) 100；
对于 100%的数据，1 \(\leq\) n, h \(\leq\) 2000，0 \(\leq\) \(a_i\) \(\leq\) 2000。

限制

1s

样例解释

样例 1：方案有 \([1, 1]\), \([2, 2]\), \([3, 3]\)、\([1, 1]\), \([2, 3]\)、\([1, 2]\), \([3, 3]\)、\([1, 3]\) 四种方案。

来源

Codeforces466D
CWOI新高二专题测试十六