"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:
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 |