## NOVICE45 - Problem 5

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 2Output: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 |