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.


-----Input-----

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).


-----Output-----

Print a single integer — the answer to the problem modulo 1000000007 (10^9 + 7).


-----Examples-----
Input
3 2
1 1 1

Output
4

Input
5 1
1 1 1 1 1

Output
1

Input
4 3
3 2 1 1

Output
0

Difficulty: HARD
Tags: Dynamic programming

Combinatorics
Skill types: Dynamic programming

Starter code:

Solutions:
mod = 10 ** 9 + 7
(n, h) = map(int, input().split())
a = list(map(int, input().split()))
dp = [[0 for j in range(h + 1)] for i in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
	need = h - a[i - 1]
	if need < 0:
		break
	if need == 0:
		dp[i][0] = dp[i - 1][0]
	else:
		dp[i][need] = (dp[i - 1][need] + dp[i - 1][need - 1]) % mod
		dp[i][need - 1] = dp[i][need] * need % mod
print(dp[n][0])


from sys import stdin, stdout

def main():
	p = 1000000007
	(n, h) = readline()
	a = list(readline())
	for i in range(n):
		a[i] = h - a[i]
		if a[i] < 0:
			return 0
	if a[0] > 1 or a[n - 1] > 1:
		return 0
	for i in range(n - 1, 0, -1):
		a[i] -= a[i - 1]
		if a[i] > 1 or a[i] < -1:
			return 0
	answer = 1
	count = 0
	for i in range(n):
		if a[i] == 1:
			count = count + 1 % p
		elif a[i] == -1:
			answer = answer * count % p
			count -= 1
		else:
			answer = answer * (count + 1) % p
	return answer

def readline():
	return map(int, stdin.readline().strip().split())
stdout.write(str(main()) + '\n')


(n, h) = list(map(int, input().split()))
a = list(map(int, input().split()))
a = [h - i for i in a]
if min(a) < 0 or a[0] > 1 or a[-1] > 1:
	print(0)
else:
	t = 1
	for i in range(1, n):
		dif = a[i - 1] - a[i]
		if dif > 1 or dif < -1:
			t = 0
		elif dif == 0:
			t *= a[i - 1] + 1
		elif dif == 1:
			t *= a[i - 1]
		t %= 1000000000 + 7
	print(t)


(n, h) = list(map(int, input().strip().split()))
l = list(map(int, input().strip().split()))
list = l
MOD = 10 ** 9 + 7
d = [[0 for i in range(h + 1)] for j in range(n + 1)]
d[0][0] = 1
for i in range(0, n):
	for balance in range(0, h + 1):
		if not d[i][balance]:
			continue
		for openState in range(2):
			for closeState in range(2):
				opens = balance + openState
				if opens + list[i] != h:
					continue
				currBalance = opens - closeState
				if 0 <= currBalance and currBalance <= h:
					m = 1
					if closeState:
						m = opens
					d[i + 1][currBalance] += m * d[i][balance]
					d[i + 1][currBalance] %= MOD
print(d[n][0])


from __future__ import print_function
from collections import defaultdict
import sys
d = defaultdict(int)
(N, h) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [0]
for a in A:
	B.append(h - a)
	if h - a < 0:
		print(0)
		sys.exit(0)
B.append(0)
MOD = 10 ** 9 + 7
d[0, False, False] = 1
for i in range(1, N + 2):
	for op in [False, True]:
		for cl in [False, True]:
			last_close = B[i - 1] - B[i] + int(op)
			if cl and B[i] == 0:
				continue
			if last_close not in [0, 1]:
				continue
			s = d[i - 1, False, bool(last_close)] + d[i - 1, True, bool(last_close)]
			if cl:
				s *= B[i]
			d[i, op, cl] = s % MOD
print(d[N + 1, False, False])


x = input().split()
n = int(x[0])
h = int(x[1])
x = input().split()
a = list((int(x[i]) for i in range(len(x))))
a.insert(0, h)
a.append(h)
sign = 0
way = 1
interval = []
start = []
end = {}
limit = 1000000007
for i in range(1, len(a)):
	if abs(a[i - 1] - a[i]) > 1 or a[i] > h:
		sign = 1
		break
	elif a[i] - a[i - 1] == -1:
		start.append(i)
	elif a[i] - a[i - 1] == 1:
		combination = len(start) - len(end.keys())
		end[i - 1] = combination
	elif a[i] == a[i - 1] and a[i] < h:
		interval.append(i)
if sign == 1:
	print(0)
else:
	for i in range(len(interval)):
		way *= h - a[interval[i]] + 1
		if way > limit:
			way = way % limit
	for i in end.keys():
		way *= end[i]
		if way > limit:
			way = way % limit
	print(way)


f = lambda : map(int, input().split())
(n, h) = f()
(s, i) = (1, 0)
for j in f():
	j = h - j
	if j < 0 or abs(j - i) > 1:
		exit(print(0))
	if j <= i:
		s = s * (j + 1) % 1000000007
	i = j
print(0 if i > 1 else s)


MOD = int(1000000000.0 + 7)
(n, h) = map(int, input().split(' '))
val = list(map(int, input().split(' '))) + [h]
pre = 1
ans = 1
for i in range(1, n + 1):
	if val[i] > h:
		ans = 0
		break
	if val[i - 1] - val[i] == 1:
		ans = pre
	if val[i - 1] - val[i] == -1:
		ans = pre * (h - val[i - 1])
	if val[i - 1] == val[i]:
		ans = pre + pre * (h - val[i])
	if abs(val[i] - val[i - 1]) > 1:
		ans = 0
		break
	pre = ans
print(ans % MOD)


(n, h) = map(int, input().split())
a = list(map(int, input().split()))
mod = 1000000007
for i in range(0, n):
	a[i] = h - a[i]
ans = 1
flag = 0
if n == 1:
	if (a[0] == 0) | (a[0] == 1):
		print(1)
	else:
		print(0)
elif (a[0] == 0) | (a[0] == 1):
	for i in range(1, n):
		k = a[i] - a[i - 1]
		if (k < -1) | (k > 1):
			print(0)
			exit(0)
		elif k == 1:
			if a[i] > 1:
				flag = flag + 1
			continue
		elif k == 0:
			ans = ans * (a[i - 1] + 1) % mod
		elif k == -1:
			ans = ans * a[i - 1] % mod
			if a[i] > 0:
				flag = flag - 1
	if flag != 0:
		print(0)
	else:
		print(ans)
else:
	print(0)


(n, h) = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
dp = [[0] * 2000 for i in range(n)]
dp[0][0] = 1 if a[0] in (h, h - 1) else 0
dp[0][1] = 1 if a[0] == h - 1 else 0
for i in range(1, n):
	opn = h - a[i]
	if opn >= 0:
		dp[i][opn] += dp[i - 1][opn]
		if opn > 0:
			dp[i][opn] += dp[i - 1][opn - 1]
		dp[i][opn] %= mod
	opn -= 1
	if opn >= 0:
		dp[i][opn] += dp[i - 1][opn + 1] * (opn + 1) + dp[i - 1][opn] + dp[i - 1][opn] * opn
		dp[i][opn] %= mod
print(dp[-1][0])


(n, h) = map(int, input().split())
a = [int(i) for i in input().split()]
dp = [0] * (n + 1)
if a[0] == h or a[0] + 1 == h:
	dp[0] = 1
MOD = 10 ** 9 + 7
for i in range(1, n):
	d = h - a[i]
	if d < 0:
		continue
	if a[i - 1] + d - 1 == h and d > 0:
		dp[i] += dp[i - 1]
	if a[i - 1] + d + 1 == h:
		dp[i] += dp[i - 1] * (d + 1)
	if a[i - 1] + d == h:
		dp[i] += dp[i - 1] * (d + 1)
	dp[i] %= MOD
if a[n - 1] == h or a[n - 1] + 1 == h:
	print(dp[n - 1])
else:
	print(0)