Superagente 86
En 1965 los teléfonos eran muy diferentes a los de hoy: el tamaño, la calidad del sonido ¡y hasta la forma de marcar! En lugar de la marcación por tonos se usaba la marcación por pulsos. Por cada dígito se hacía girar un disco una cantidad que dependía del propio dígito. En función de la longitud del giro, se emitían por la línea uno o varios pulsos, que la centralita era capaz de contar para reconocer el número. El dígito 1 emitía un pulso, el 2 enviada dos, y así sucesivamente, con la peculiaridad de que el 0 emitía 10. Entre dígito y dígito se producía una pausa hasta que el usuario giraba de nuevo el disco.
Maxwell Smart, el Superagente 86, ha interceptado desde su zapatófono una llamada entre agentes de KAOS. Por desgracia, lo único que tiene es la longitud total de la marcación en número de pulsos. Sabe que entre dígito y dígito transcurre el tiempo asociado a un pulso, pero no sabe más. ¡Ni siquiera cuántos dígitos tenía el número!
Maxwell no se distingue por su audacia, y tiene la tonta idea de que solo con la longitud de la marcación podrá saber el número que ha marcado el agente de KAOS. La Agente 99 insiste en que eso es imposible, pero no consigue convencerle.
Entrada
La entrada comienza con un número indicando cuántos casos de prueba habrá que procesar. Cada caso de prueba es un número 1 ≤ n ≤ 10.000 con la longitud, en pulsos, de la marcación.
Cada dígito i necesita i pulsos para ser marcado, salvo el 0, que necesita 10. Además, el tiempo entre dígito y dígito cuenta como un pulso adicional.
Salida
Por cada caso de prueba el programa escribirá cuántos números de teléfono distintos existen que requieren ese número de pulsos para ser marcados. Como el número puede ser muy alto, se calculará módulo 1.000.000.007.
Entrada de ejemplo
4 1 2 3 10
Salida de ejemplo
1 1 2 55