Trên hệ trục tọa độ Oxy, Bờm lần lượt đặt ~N~ viên bi, viên bi thứ ~i~ có tọa độ ~(0, i)~. Ở mỗi lượt chơi sau đấy, Bờm có ba lựa chọn:

• Không làm gì cả.
• Chọn một viên bi, di chuyển lên trên 1 đơn vị, nếu viên bi ở vị trí ~(x, y)~, ta có thể đưa viên bi về vị trí ~(x + 1, y)~.
• Chọn một viên bi, di chuyển xuống dưới 1 đơn vị, nếu viên bi ở vị trí ~(x, y)~, ta có thể đưa viên bi về vị trí ~(x - 1, y)~.
• Sau ~K~ lượt chơi, ~N~ viên bi lần lượt kết thúc ở các tọa độ ~(x_1, 1), (x_2, 2), (x_3, 3), \dots, (x_N, N)~.

Yêu cầu: Đếm số cách đi khác nhau của Bờm modulo ~10^9 + 7~ để từ trạng thái ban đầu, sau ~K~ lượt đi, các viên bi ở trạng thái đích. Hai cách chơi được gọi là khác nhau, nếu như tồn tại một lượt chơi mà thao tác ở cách chơi này khác thao tác ở cách chơi kia.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~ ~(1 \le N \le 100, 1 \le K \le 1000)~, lần lượt là số lượng viên bi và số lượt mà Bờm đã chơi.
• Dòng tiếp theo gồm ~N~ số nguyên ~x_i~ ~(-1000 \le x_i \le 1000)~, số nguyên thứ ~i~ biểu diễn viên bi thứ ~i~ kết thúc ở tọa độ ~(x_i, i)~.

Output

• In ra một số nguyên duy nhất là số cách di chuyển những viên bi ~MOD 10^9 + 7~.

Sample Input 1

2 2
1 -1

Sample Output 1

2

Sample Input 2

5 20
1 2 3 4 5

Sample Output 2

182783854