408512: GYM103176 E Eat More

HML loves eating!

He has $$$N$$$ dishes on his table. Each dish has its own saltiness value, denoted as $$$A_i$$$ for the $$$i$$$-th dish.

HML also has a saltiness preference value $$$K$$$. He wants to split the dishes into some groups (possibly one group), and each group forms a consecutive contiguous subsegment of the original dishes. So every dish will be in exactly one group and for the $$$i^{th}$$$ group, it contains dishes $$$l_i$$$, $$$l_i + 1$$$, ..., $$$r_i$$$. Also, for every group, the absolute value of the sum of saltiness of the dishes belong to the group, should be less than or equal to $$$K$$$. For example, if the group contains dishes $$$l$$$, $$$l + 1$$$, ..., $$$r$$$, then $$$|\sum_{i=l}^{r} A_i|\le K$$$, where $$$|x|$$$ denotes the absolute value of $$$x$$$.

HML is a curious boy, he wonders how many ways there are to group the dishes. As the number could be large, please output the answer modulo $$$10^9 + 7$$$.

The first line consists of two integers, $$$N$$$ and $$$K$$$ ($$$1\le N\le 10^5$$$, $$$0\le K\le 10^{14}$$$).

The second line consists of $$$N$$$ integers, which is the array $$$A$$$. The $$$i$$$-th integer correspond to $$$A_i$$$ ($$$-10^9\le A_i\le 10^9$$$).

Output the total number of ways to group the food modulo $$$10^9 + 7$$$.

4 1
2 -1 -1 0

4

6 2
2 -1 3 -2 0 1

19

In sample 1, there are 4 ways:

1. [2 -1] [-1 0]
2. [2 -1] [-1] [0]
3. [2 -1 -1] [0]
4. [2 -1 -1 0]