NOVICE45 - Problem 5

no tags 

 

Mahesh and I are always at conflict, Where I am a lazy person who would rather apply bruteforce and compute all possibilities of a problem to find the answer, he would rather solve it on paper to find a mathematical formula and reduce computational time. Fed up of his daily taunts I formulated the following problem, lets see who wins here bruteforce or mathematical precalculation:
Given two positive integers N and K you have to find the number of distinct ways of writing N as the sum of integers(possibly only 1) in range of [1,K] (inclusive).
For example if N = 4 and K = 2, we have these 3 ways => (2+2), (2+1+1), (1+1+1+1).

 

Mahesh and I are always at conflict, Where I am a lazy person who would rather apply bruteforce and compute all possibilities of a problem to find the answer, he would rather solve it on paper to find a mathematical formula and reduce computational time. Fed up of his daily taunts I formulated the following problem, lets see who wins here bruteforce or mathematical precalculation:

Given two positive integers N and K you have to find the number of distinct ways of writing N as the sum of integers(possibly only 1) in range of [1,K] (inclusive).

For example if N = 4 and K = 2, we have these 3 ways => (2+2), (2+1+1), (1+1+1+1).

 

 

Input

 

Line 1: T(number of test cases)

Line 2 to T+1: 2 space seprated integers N,K. (1<=N<=10000 and 1<=K<=100) 

 

Output

1 line per test case telling the number of ways. Since the answer can be very large print it modulo 1000000007.

Example

Input:
3
1 10
2 1
4 2

Output:
1
1
3


Added by:Mahesh Chandra Sharma
Date:2011-03-01
Time limit:0.219s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem