Limits
2s, 512 MB

**"Whosoever holds this hammer, if he be worthy, shall possess the power of Thor."**

This inscription was carried with Mjolnir (The hammer).

As the Norse god of thunder, Thor can summon the elements of the storm (lightning, rain, wind, snow) and uses Mjolnir as a tool to focus this ability.

However, Mjolnir was destroyed by Hela ( Sister of Thor) . Thor has now Stormbreaker which is an enchanted axe. It was forged from Uru on Nidavellir. Eitri ( A friend of Thor) claimed the weapon was meant to become the strongest weapon in Asgard's history.

Thanos (The great villain) is coming. He has a large army of size **N**. Every enemy has a different kind of strength. They are arranged in a line. Thor decided to defeat them all and he will attack the enemies with lightning. In each attack, Thor can reduce the total of **X** strength of the enemy. Thor doesn't want to attack more than **K** times.

So, Thor want to divide N enemies at most K groups such that every group total strength doesn't exceed X. As the enemy are arranged in a line. So he has to divide the groups in a **consecutive** manner. A group can't empty in size.

The first line consist of 3 integers N, K and X as described above.

The second line contains N integer a1, a2,..... an , which represent the strength of Thanos's army which are ordered as they appear in the war.

ai represent the strength of ith enemy.

**Constraint:**

- 1 <= N <= 104
- 1 <= K <= 109
- 1 <= X <= 109
- 1 <= ai <= 109

Print the answer how many ways Thor can divide the enemy in at most K groups such that each group total strength doesn't exceed X. As the answer can be very large, you have to print the answer modulo **109 + 7**

Input | Output |
---|---|

3 3 6 1 2 3 | 4 |

Input | Output |
---|---|

5 3 3 1 2 3 2 1 | 1 |