Las máquinas utilizan la notación binaria para almacenar información. De esta forma, los números son representados utilizando únicamente los dígitos 0 y 1. A cada uno de esos dígitos se le llama bit. Igual que ocurre con la notación decimal, la longitud (en cantidad de dígitos) que usemos limita la cantidad de números que podremos representar. Cuando (en decimal) tenemos un número de hasta 3 dígitos, podremos representar 1000 números distintos (del 0 al 999). En binario con 3 dígitos podremos representar hasta 8 números distintos (del 0 al 7, que en binario se escribe 111).
La representación binaria puede también utilizarse para lo que se conoce como máscaras de bits que no es más que darle un significado distinto a cada uno de los bits a 1 de un número binario.
Dada la longitud de un número o máscara de bits (o el número de bits disponibles), ¿cuántos números distintos hay que tengan K bits a 1?
La entrada está formada por una serie de consultas, cada una en una línea independiente. Las líneas tendrán dos números mayores o iguales que 0; el primero, n, indica el número de dígitos total del número y el segundo, k, el número de bits a 1 por el que se pregunta. Ninguno de los dos valores será superior a 1.000.
La consulta 0 0 marca el final de la entrada y no debe procesarse.
Para cada caso de prueba se mostrará en una línea la cantidad de números binarios de n bits que tienen k bits a 1 módulo 1.000.000.007.
2 0 2 1 4 2 5 2 0 0
1 2 6 10