Contando Hipérdromos


Submit solution

Points: 100 (partial)
Time limit: 2.5s
Memory limit: 256M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

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.


Comments

There are no comments at the moment.