Quy hoạch động cổ điển

Cho mảng số nguyên ~A~ gồm ~N~ phần tử được đánh số từ ~1~ đến ~N~ và một số nguyên dương ~S~.

Hàm ~f(i,j)~ được định nghĩa là số lượng dãy số ~\{x_1,x_2,...,x_k\}~ thỏa mãn đồng thời hai điều kiện:

• ~i \le x_1 < x_2 < ... < x_k \le j~
• ~A_{x_1} + A_{x_2} + ... + A_{x_k}=S~

Yêu cầu tính giá trị biểu thức sau:

$$\displaystyle \sum_{l=1}^{N} \sum_{r=l}^{N} f(l,r)$$

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~S~ ~(1 \le N \le 5000~ ; ~1 \le S \le 5000)~.
• Dòng thứ hai chứa ~N~ số nguyên ~A_i~ ~(1 \le A_i \le 5000)~.

Output

• In ra giá trị biểu thức cần tính, kết quả chia lấy dư cho ~10^9+7~.

Examples

3 2
1 1 2

5

Scoring

• Subtask ~1~ ~-~ ~750~ điểm: ~N \le 5~
• Subtask ~2~ ~-~ ~750~ điểm: ~N\le 100~ ; ~S \le 100~
• Subtask ~3~ ~-~ ~1000~ điểm: Không có ràng buộc gì thêm

Notes

Trong ví dụ, các giá trị hàm ~f(l,r)~ như sau:

• ~f(1,1)=0~
• ~f(1,2)=1~, các dãy số thỏa mãn: ~\{1,2\}~
• ~f(1,3)=2~, các dãy số thỏa mãn: ~\{1,2\}~, ~\{3\}~
• ~f(2,2)=0~
• ~f(2,3)=1~, các dãy số thỏa mãn: ~\{3\}~
• ~f(3,3)=1~, các dãy số thỏa mãn: ~\{3\}~