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