Di chuyển vị trí

Đã 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ủ 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,\dots ,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$. $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.

Dữ liệu vào

• 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$).

Dữ liệu vào đảm bảo luôn có cách di chuyển.

Dữ liệu ra

In 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, hãy in ra phần dư của kết quả khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le n\le 100$, $1\le T\le 1000$.
• $|A_i|\le 1000$ với $1\le i\le n$.
• Luôn tồn tại ít nhất một cách di chuyển.

Subtasks

Điểm được tính theo từng test.

• Subtask 1 ($25\%$ số test): $n,T\le 5$.
• Subtask 2 ($25\%$ số test): ${\sum }_{i=1}^n|A_i|=T$.
• Subtask 3 ($25\%$ số test): $n=1$.
• Subtask 4 ($25\%$ số test): không có ràng buộc gì thêm.

Ví dụ