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 10⁵ 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 A_i kept on the i^th 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, A_i (number of stones kept on i^th 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 <= A_i <= 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.