MOWGLI - Time for Revenge

Mowgli is a little boy brought up by a wolf pack in the jungle. The king of jungle Shere Khan wants the boy for revenge. Foreseeing his danger Akela the leader of wolf pack suggests Mowgli to leave the jungle. Before Mowgli's departure from jungle, he got the news that Shere Khan killed Akela. So Mowgli wants revenge. He wants to get back to Shere Khan's palace in shortest path.

There are N number of rivers in his path. Width of each river is at most 105 meters. To cross the river stones are kept at a distance of 1 meter. Mowgli can jump across at most K stones at a time. Given total number of stones Ai kept on the ith river. Your job is to tell total number of ways Mowgli can cross each river. As answer can be very large, give output modulo 1000000007.

Input

There are around 10 test cases.

First line contains an integer T number of test cases

Each test case consists of two lines:

First line contains two integers  N (number of rivers) and K (maximum number of stones Mowgli can skip).

Next line contains N integers, Ai (number of stones kept on ith river).

Output

One line for each river.

Total number of ways Mowgli can cross the river.

Constraints:

T <= 10

1 <= N <= 100

0 <= K <= 50

0 <= Ai <= 100000

Example

Input:
1
2 1
1 2

Output:
2
3

Explanation

For second river with 2 stones. Mowgli can jump across 1 stone maximum at a time. So there are three choices

  1. Start → 1st → 2nd → Destination.
  2. Start → 1st → Destination.
  3. Start → 2nd → Destination.

Added by:সুশি
Date:2016-06-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Abhisek Banerjee

hide comments
2017-02-05 22:01:31
Only bottom up works :/
2016-06-15 13:42:59
@Susi Please explain with some more test cases. Unable to understand the problem statement.

Re: No more test cases will be provided. I think given explanation is sufficient.

Last edit: 2016-06-15 14:22:41
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.