Tiradas del parchís
El parchís es un conocido juego de mesa de fichas y dados donde los jugadores deben conseguir llevar las fichas de su color desde su "casa" hasta la meta. La parte principal del tablero crea un circuito de 68 casillas, y dispone además de un pasillo de cada color de 8 posiciones más. Las fichas comienzan en una posición del tablero diferente según su color, y no recorren el circuito entero, sino que, cuando están a punto de hacerlo, se desvían por el pasillo de su color que las lleva hasta la meta.
Los jugadores lanzan, de forma alterna, un dado que indica el número de casillas que deben hacer avanzar alguna de sus fichas. Estas deben alcanzar la meta de forma exacta cuando llegan al final. De otro modo rebotarán volviendo hacia atrás a lo largo del pasillo de su color.
Existen varias reglas adicionales e infinidad de variantes (comer fichas, casillas seguras, bloqueos, jugar con dos dados…) pero ignorando todas ellas, ¿de cuántas formas distintas se puede conseguir hacer llegar una ficha a su destino?
Entrada
Cada caso de prueba son dos números. El primero, entre 1 y 40.000, indica el número de casillas que una determinada ficha de parchís debe recorrer desde su posición actual hasta alcanzar la meta. El segundo, entre 1 y 40, indica el número de caras del dado con el que se juega.
Como mucho habrá 5.000 casos de prueba y la mayoría serán con números de casillas moderados.
Salida
Por cada caso de prueba el programa escribirá cuántas secuencias distintas de tiradas de dados existen que hacen que la ficha termine, de forma exacta, en la meta, sin rebotar ninguna vez. Como el número es grande, se dará módulo 999.999.999.989.
Entrada de ejemplo
4 1 4 2 2 5
Salida de ejemplo
1 5 2