MOG
Spanish
|
English

Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

ACM 2015 - Round #2

Ended

D - Desafio de Fito

Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)

Leyendo en un libro muy antiguo Fito se encontró un desafío muy interesante. Este consiste en que se tiene una fila de personas y hay que determinar de cuántas formas se pueden seleccionar $K$ de ellas, de forma tal que no haya dos que estén paradas consecutivamente.

Input

La entrada tendrá varios casos de prueba que serán a lo sumo $100$. Cada caso estará compuesto por una línea con dos enteros $N$ $(1 \le N \le 10^9)$ y $K$ $(1 \le K \le 10^5)$, que representan la cantidad de personas en la fila y la cantidad que hay que seleccionar respectivamente. La última línea tendrá dos ceros y no debe ser procesada.

Output

Por cada caso de prueba se debe imprimir una línea con la cantidad de formas de seleccionar las $K$ personas. Como el resultado puede ser muy grande usted debe calcularlo módulo $10^9+7$.

Sample test(s)

Input
3 2 4 2 0 0
Output
1 3