Dada una cadena que consisten de solo letras 'X' y 'Y'. Una cadena se llama "Super cadena" si:

a) la cadena no tiene caracteres de tipo 'X' por delante

b) la cadena no tiene P caracteres consecutivos de tipo 'X'.

tu tarea es encontrar el numero de "Super cadenas" de longitud N

La primera linea contiene un numero T (1<= T <= 100) la cantidad de casos de prueba.

Cada caso consiste en dos enteros separados N y P (1 <= N <= 10000, 1 <= P <= 10).

Por cada caso de prueba imprimir el numero total de "Super cadenas" de longitud N modulo 1000000007

para el primer ejemplo: la unica cadena posible es YY

para el segundo ejemplo: las cadenas posibles son: YXYX, YXYY, YYYX, YYXY, YYYY.