ZOJ Monthly, June 2009 - D

Compositions

---

Time Limit: 5 Seconds      Memory Limit: 32768 KB

---

We consider problems concerning the number of ways in which a number can be written as a sum. If the order of the terms in the sum is taken into account the sum is called a composition and the number of compositions of n is denoted by c(n). Thus, the compositions of 3 are

• 3 = 3
• 3 = 1 + 2
• 3 = 2 + 1
• 3 = 1 + 1 + 1

So that c(3) = 4.

Suppose we denote by c(n, k) the number of compositions of n with all summands at least k. Thus, the compositions of 3 with all summands at least 2 are

• 3 = 3

The other three compositions of 3 all have summand 1, which is less than 2. So that c(3, 2) = 1.

Input

The first line of the input is an integer t (t <= 30), indicate the number of cases.

For each case, there is one line consisting of two integers n k (1 <= n <= 10⁹, 1 <= k <= 30).

Output

Output c(n, k) modulo 10⁹ + 7.

Sample Input

2
3 1
3 2

Sample Output

4
1

---

Author: GAO,Yuan
Source: ZOJ Monthly, June 2009
Submit    Status