Trong giờ tự học, Norman đã đưa ra một bài toán rất khó để thách thức Emma và những đứa trẻ khác. Cậu cho trước một dãy số nguyên gồm \(n\) phần tử và yêu cầu mọi người tìm cách đưa giá trị của tất cả các phần tử này về cùng bằng một số \(h\). Cậu cho phép mọi người thực hiện vô số bước, mỗi bước được chọn một đoạn con liên tiếp \([l,r]\) và tăng tất cả phần tử trong đoạn lên 1 đơn vị. Tuy nhiên, Norman đưa ra luật là đoạn con được chọn phải không được trùng vị trí đầu hay vị trí cuối với bất kì đoạn con nào được chọn trước đó. Nói cách khác, mỗi cặp đoạn con được chọn \([l_1,r_1],[l_2,r_2]\) phải thỏa mãn \(l_1 \neq l_2\) và \(r_1 \neq r_2\). Emma rất nhanh trí và thông minh nên đã dễ dàng tìm được một lời giải thỏa mãn yêu cầu đề bài. Tưởng chừng bài toán của Norman chỉ dễ dàng xơi thế nhưng rồi Norman yêu cầu phải đưa ra tổng số lượng cách giải khác nhau. Emma đã cố gắng mò mẫn tính toán nhưng kết quả bài toán quá lớn, đành phải nhờ đến khả năng lập trình của các Coders thông thái thôi!

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n,h\) \((h \leq 2000)\).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1,a_2,\cdots,a_n (0 \leq a_i \leq 2000)\).

Output

• Đưa ra một số nguyên duy nhất là phần dư kết quả bài toán khi chia cho \(10^9+7\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \leq 10\).
• Subtask \(2\) (\(50\%\) số điểm): \(n \leq 2000\).

Example

3 2
1 1 1            

4