题目描述

给出 n 项的数列，要求将数列划分成若干段，且每一段之和都不超过 s。求一共有多少种满足要求的划分方法。

方法数很大，只要求输出除以 10^9 的余数。

输入格式

第 1 行，两个正整数 n, s。

第 2 行，n 个正整数 a1, a2, …, an。

输出格式

一个整数，划分方法数除以 10^9 的余数。

输入样例 #1

5 3
1 2 1 1 1

输出样例 #1

10

输入样例 #2

5 7
1 6 6 2 7

输出样例 #2

2

输入样例 #3

8 9
7 8 3 4 3 4 1 9

输出样例 #3

10

数据范围与约定

1 ≤ n ≤ 1000，

1 ≤ ai ≤ 1000，

1 ≤ s ≤ 10000。