# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Mighty Thor

**“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.

## Input

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

The second line contains N integer a_{1}, a_{2},….. a_{n }, which represent the strength of Thanos’s army which are ordered as they appear in the war.

a_{i} represent the strength of i^{th} enemy.

**Constraint:**

- 1 <= N <= 10
^{4} - 1 <= K <= 10
^{9} - 1 <= X <= 10
^{9} - 1 <= ai <= 10
^{9}

## Output

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 **10 ^{9} + 7**

## Samples

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

3 3 6 1 2 3 | 4 |

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

5 3 3 1 2 3 2 1 | 1 |

0% Solution Ratio

Login to submit