Đã lâu lắm rồi Phú không chơi điện tử. Để chuẩn bị cho tinh thần thoải mái khi bước vào buổi thi lập trình tại vào tuần sau, Phú quyết định bật máy tính lên và tham gia chơi một trò chơi. Trên giao diện bắt đầu của trò chơi có ~n~ xạ thủ được xếp thành một hàng ngang, các xạ thủ được đánh số từ 1 đến ~n~ từ trái sang phải. Phía trước các xạ thủ có một mục tiêu cần phá hủy. Để nhắm vào những vị trí điểm yếu của mục tiêu, Phú bỏ ra ~T~ giây để di chuyển vị trí của các xạ thủ. Tại giây thứ i (~1 \le i \le T~) Phú có thể thực hiện một trong 3 thao tác sau:

• Nháy chuột trái vào xạ thủ thứ ~j~ bất kỳ (~1 \le j \le n~) khi đó xạ thủ thứ ~j~ sẽ bước sang bên trái một bước.
• Nháy chuột phải vào xạ thủ thứ ~k~ bất kỳ (~1 \le k \le n~) khi đó xạ thủ thứ ~k~ sẽ bước sang bên phải một bước.
• Không thực hiện việc gì (để cho tay nghỉ ngơi cho đỡ mỏi).

Biết rằng sau đúng ~T~ giây, vị trí mới của các xạ thủ so với vị trí cũ của họ tạo thành một dãy số nguyên ~A_1,A_2,..,A_n.~ Trong đó ~|A_i | (1 \le i \le n)~ là khoảng cách (tính bằng đơn vị bước) giữa vị trí hiện tại của xạ thủ i so với vị trí ban đầu của xạ thủ i. Chú ý ~A_i~ dương nếu vị trí hiện tại ở bên phải so với vị trí ban đầu, ~A_i~ âm nếu vị trí hiện tại ở bên trái so với vị trí ban đầu. Lưu ý là tại một thời điểm hai xạ thủ khác nhau có thể đứng cùng một vị trí.

Yêu cầu: Hãy cho biết Phú có bao nhiêu cách thực hiện việc di chuyển vị trí của các xạ thủ để được dãy A như trên. Hai cách di chuyển được gọi là khác nhau, nếu như tồn tại ít nhất một giây trong ~T~ giây mà thao tác ở cách di chuyển này khác thao tác ở cách di chuyển kia.

Input: dòng đầu tiên chứa hai số nguyên ~n~ và ~T~ (~1 \le n \le 100;1 \le T \le 1000~). Dòng thứ hai gồm ~n~ số nguyên ~A_1,A_2,..,A_n~ trong đó ~|A_i | \le 1000~ với ~1 \le i \le n.~

Output: một số nguyên duy nhất là số cách di chuyển tìm được. Do số cách có thể rất lớn, bạn hãy lấy kết quả chia dư cho ~10^9+7~. Dữ liệu vào đảm bảo luôn có cách dịch chuyển.

Sample input 1:

2 2

-1 1

Sample output 1:

2

Sample input 2:

2 3

-1 0

Sample output 2:

12

* Giải thích:*

Ở ví dụ 1:

• Cách 1: Giây 1 T(1), giây 2 P(2).
• Cách 2: Giây 1 P(2), giây 2 T(1).

Ở ví dụ 2:

• Cách 1: Giây 1 T(1), giây 2 None, giây 3 None.
• Cách 2: Giây 1 T(1), giây 2 T(2), giây 3 P(2).
• Cách 3: Giây 1 T(1), giây 2 P(2), giây 3 T(2).
• Cách 4: Giây 1 T(1), giây 2 P(1), giây 3 T(1).
• Cách 5: Giây 1 T(1), giây 2 T(1), giây 3 P(1).
• Cách 6: Giây 1 P(1), giây 2 T(1), giây 3 T(1).
• Cách 7: Giây 1 None, giây 2 T(1), giây 3 None.
• Cách 8: Giây 1 None, giây 2 None, giây 3 T(1).
• Cách 9: Giây 1 T(2), giây 2 T(1), giây 3 P(2).
• Cách 10: Giây 1 T(2), giây 2 P(2), giây 3 T(1).
• Cách 11: Giây 1 P(2), giây 2 T(2), giây 3 T(1).
• Cách 12: Giây 1 P(2), giây 2 T(1), giây 3 T(2).

trong đó:

• T(i) - nháy chuột trái vào xạ thủ thứ i;

• P(i) - nháy chuột phải vào xạ thủ thứ i;

• None - không làm gì cả.