Peter có một dãy số nguyên ~a_1, a_2, \dots, a_n~. Peter muốn tất cả các số trong dãy trở thành ~h~. Anh ta có thể thực hiện thao tác "cộng một trên đoạn ~[l, r]~": cộng thêm ~1~ vào tất cả các phần tử trong dãy có chỉ số từ ~l~ đến ~r~ (bao gồm cả hai đầu).

Tuy nhiên, Peter không bao giờ chọn bất kỳ phần tử nào làm điểm bắt đầu của đoạn hai lần. Tương tự, Peter cũng không bao giờ chọn bất kỳ phần tử nào làm điểm kết thúc của đoạn hai lần. Nói cách khác, với hai đoạn bất kỳ ~[l_1, r_1]~ và ~[l_2, r_2]~, nếu Peter đã thực hiện thao tác trên hai đoạn này thì các bất đẳng thức sau phải được đồng thời thỏa mãn: ~l_1 \neq l_2~ và ~r_1 \neq r_2~.

Hỏi có bao nhiêu cách khác nhau để biến tất cả các số trong dãy thành ~h~? In ra kết quả này theo modulo ~10^9 + 7~. Hai cách được coi là khác nhau nếu một trong chúng có một đoạn mà cách còn lại không có.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~h~ ~(1 \leq n, h \leq 2000)~.

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(0 \leq a_i \leq 2000)~.

Output

In ra một số nguyên duy nhất – đáp án của bài toán theo modulo ~10^9 + 7~.

Sample Input 1

3 2
1 1 1

Sample Output 1

4

Sample Input 2

5 1
1 1 1 1 1

Sample Output 2

1

Sample Input 3

4 3
3 2 1 1

Sample Output 3

0