Increase Sequence

题意翻译

**题目大意**： 给定一个序列，可以对若干对区间$[l,r]$中的数+$1$，且保证任意两个区间的左右端点不重合（即$l_1$!=$l_2$且$r_1$!=$r_2$）。 最终要求序列中所有元素值都等于$h$，请输出总方案数对$1e9$+$7$取模后的结果。 ------------ **输入格式**： 第一行两个数字$n$和$h$。 接下来一行$n$个数字$a_i$。 ------------ **输出格式**： 共一行，为总方案数对$1e9$+$7$取模后的结果。 ------------ **数据范围**： $1$≤$n,h$≤$2000$ $0$≤$a_i$≤$2000$

题目描述

Peter has a sequence of integers $ a_{1},a_{2},...,a_{n} $ . Peter wants all numbers in the sequence to equal $ h $ . He can perform the operation of "adding one on the segment $ [l,r] $ ": add one to all elements of the sequence with indices from $ l $ to $ r $ (inclusive). At that, Peter never chooses any element as the beginning of the segment twice. Similarly, Peter never chooses any element as the end of the segment twice. In other words, for any two segments $ [l_{1},r_{1}] $ and $ [l_{2},r_{2}] $ , where Peter added one, the following inequalities hold: $ l_{1}≠l_{2} $ and $ r_{1}≠r_{2} $ . How many distinct ways are there to make all numbers in the sequence equal $ h $ ? Print this number of ways modulo $ 1000000007 (10^{9}+7) $ . Two ways are considered distinct if one of them has a segment that isn't in the other way.

输入输出格式

输入格式

The first line contains two integers $ n,h $ $ (1<=n,h<=2000) $ . The next line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ $ (0<=a_{i}<=2000) $ .

输出格式

Print a single integer — the answer to the problem modulo $ 1000000007 (10^{9}+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