Peter has a sequence of integers a1, a2, ..., an. 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 [l1, r1] and [l2, r2], where Peter added one, the following inequalities hold: l1 ≠ l2 and r1 ≠ r2.

How many distinct ways are there to make all numbers in the sequence equal h? Print this number of ways modulo 1000000007 (109 + 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 a1, a2, ..., an (0 ≤ ai ≤ 2000).

Output

Print a single integer — the answer to the problem modulo 1000000007 (109 + 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
from sys import stdin, stdout


def main():
    p = 1000000007  # Constante brindada por el problema
    n, h = readline()
    a = list(readline())
    for i in range(n):  # Se calculan las diferencias entre h y los numeros de la secuencia
        a[i] = h - a[i]
        if a[i] < 0:  # El valor del numero es superior al de h deseado
            return 0
    if a[0] > 1 or a[n - 1] > 1:  # Es imposible que uno de los extremos alcance el valor de h
        return 0
    for i in range(n - 1, 0, -1):  # Se calculan las diferencias entre los valores de las posiciones consecutivas
        a[i] -= a[i - 1]
        if a[i] > 1 or a[i] < -1:  # La diferencia es superior a la necesaria para que haya solucion
            return 0
    answer = 1
    count = 0
    for i in range(n):
        if a[i] == 1:  # Existe un segmento que se inicia en esta posicion
            count = count + 1 % p
        elif a[i] == -1:  # Existe un segmento que termina en la posicion anterior
            answer = answer * count % p
            count -= 1
        else:  # No ocurre ninguno de los dos casos anteriores, o ambos a la vez
            answer = answer * (count + 1) % p
    return answer


def readline():  # Metodo para leer una linea completa, dividirla en elementos y convertirlos en numeros enteros
    return map(int, stdin.readline().strip().split())


if __name__ == '__main__':
    stdout.write(str(main()) + '\n')
