Đã lâu lắm rồi Cuội 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 Trại hè Hùng Vương vào ngày mai, Cuội 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ải phá hủy. Để nhắm vào những vị trí điểm yếu của mục tiêu, Cuội 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~) Cuội có thể thực hiện một trong ~3~ thao tác sau:

• Nháy chuột trái vào xạ thủ ~j~ bất kỳ (~1 \le j \le n~) khi đó xạ thủ ~j~ sẽ bước sang bên trái một bước.
• Nháy chuột phải vào xạ thủ ~k~ bất kỳ (~1 \le k \le n~) khi đó xạ thủ ~k~ sẽ bước sang bên phải một bước.
• Không thực hiện 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, \dots, A_n~. Trong đó ~|A_i|~ (~1 \le i \le n~) là khoảng 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~. ~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 Cuội 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, \dots, A_n~ (~|A_i| \le 1000~ với ~1 \le i \le n~).

Output

• Ghi ra 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

Subtasks