
ZOJ Problem Set  3216
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
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
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^{9}, 1 <= k <= 30). Output Output c(n, k) modulo 10^{9} + 7. Sample Input 2 3 1 3 2 Sample Output 4 1 Author: GAO,Yuan Source: ZOJ Monthly, June 2009 