← 返回题目列表

Codeforces · 466/D

D. 增加顺序

中文机器翻译题面 查看原题

Peter 有一个整数序列 a1, a2, ..., an。 Peter 希望序列中的所有数字都等于 h。他可以执行“在段[l,r]上加一”的操作:对序列中索引从l到r(含)的所有元素加一。此时,Peter 从未两次选择任何元素作为该段的开头。同样,Peter 也不会两次选择任何元素作为段的结尾。换句话说,对于任意两个线段 [l1, r1] 和 [l2, r2](其中 Peter 添加了一个),以下不等式成立:l1 ≠ l2 且 r1 ≠ r2。

有多少种不同的方法可以使序列中的所有数字都等于 h?打印此数对 1000000007 取模 (109 + 7)。如果其中一种方式具有另一种方式中不存在的段,则两种方式被认为是不同的。

输入

第一行包含两个整数 n, h (1 ≤ n, h ≤ 2000)。下一行包含 n 个整数 a1, a2, ..., an (0 ≤ ai ≤ 2000)。

输出

打印一个整数——问题的答案以 1000000007 (109 + 7) 为模。

示例

输入 #1

3 2
1 1 1

输出 #1

4

输入 #2

5 1
1 1 1 1 1

输出 #2

1

输入 #3

4 3
3 2 1 1

输出 #3

0