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: interview

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

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

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

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

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

n,h=list(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)
else:
    if((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)
                return
            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)


MOD = int(1e9 + 7)
n, h = list(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 = [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)

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(list(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 list(end.keys()):
        way *= end[i]
        if way > limit:
            way = way % limit
    print(way)


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
        else:
            if dif == 0:t*=(a[i-1]+1)
            elif dif == 1:t*=(a[i-1])
        #print(t)
        t%=(1000000000+7)
    print(t)


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: print(0);return
    if j <= i: s = s * (j + 1) % 1000000007
    i = j
print(0 if i > 1 else s)


from collections import defaultdict

import sys

d = defaultdict(int)

#input = raw_input

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)
        return
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 # can't close anything
            if last_close not in [0, 1]: continue # doesn't add up
            s = d[i-1, False, bool(last_close)] + d[i-1, True, bool(last_close)]
            if cl: s *= B[i]
            #if i == 2 and op:
            #    print(cl, s, last_close,
            #          d[i-1, False, bool(last_close)] ,
            #          d[i-1, True, bool(last_close)])
            d[i, op, cl] = s % MOD

#print(d)

#for i in range(N+2):
#    print("\n", i, end=": ")
#    for op in [False, True]:
#        for cl in [False, True]:
#            print(d[i, op, cl], end=" ")
#print()



print(d[N+1, False, False])


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
        else:
            if dif == 0:t*=(a[i-1]+1)
            elif dif == 1:t*=(a[i-1])
        #print(t)
        t%=(1000000000+7)
    print(t)