Halla la cantidad de números hipérdromos válidos en base ~b~, que tienen a lo más ~n~ dígitos.

Un número es hipérdromo si se pueden reordenar sus dígitos y obtener un palíndromo. Un número es palíndromo si se lee igual de izquierda a derecha que de derecha a izquierda. Un número es válido si no tiene ceros a la izquierda (no importa si al reordenarlo, para convertirlo en palíndromo, quedan ceros a la izquierda, lo importante es que el número inicial no los tenga).

Nota que el número ~0~ es válido.

Entrada

La primera y única línea contiene los enteros ~n~ y ~b \; (1 \leq n \leq 10^9; 2 \leq b \leq 7)~.

Salida

En una única línea imprima la respuesta del problema. Como esto puede ser muy grande imprímela módulo ~10^9 + 7 \; (1000000007)~.

Ejemplo de entrada

3 2

Ejemplo de salida

7

Explicación del ejemplo

Los números son: ~0, 1, 11, 100, 101, 110~ y ~111~.