El código de la T.I.A.
Ante la nueva oleada de ataques a las redes de otras agencias de investigación, la T.I.A. ha decidido tomarse en serio la transmisión de sus mensajes entre las distintas oficinas y ha contratado los servicios de un especialista que se hace llamar Pepe Gotera.
A la vista de la solución del supuesto experto, salta a la vista que vive anclado en el pasado. Lo único que ha hecho ha sido asignar a cada símbolo un número de entre uno y tres dígitos y ha instruido a los agentes especiales para que, cuando tengan que mandar un mensaje, simplemente sustituyan las letras y símbolos del mensaje por esos códigos, dando lugar a una secuencia de números, uno detrás de otro.
Por ejemplo, en una codificación donde la A es sustituida por el 12 y la B es sustituida por el 42, el grupo musical ABBA se codifica 12424212.
Pepe Gotera además de dar el método de encriptado ha proporcionado distintas tablas de codificación que los agentes irán utilizando a lo largo del tiempo. Sin embargo, nuestro "experto" no ha oído hablar de los códigos de Huffman* ni nada que se le parezca, por lo que cuando le ha llegado a Otilio el primer mensaje cifrado con una de esas tablas, se ha dado cuenta de que en realidad hay varios posibles descifrados distintos. El pánico se ha instalado en las oficinas centrales de la T.I.A. y cuando le han pedido explicaciones a Pepe Gotera ha dicho que, dado que ninguno de los códigos de las letras contiene ceros, se puede decir a los agentes que utilicen ceros para separar palabras.
El Super no está aún convencido de la efectividad de la solución, así que nos ha pedido ayuda. Dada la tabla de símbolos y un texto cifrado, ¿de cuántos mensajes distintos podría provenir?
Entrada
La entrada estará compuesta por distintos casos de prueba, terminados con una línea con un 0.
Cada caso de prueba está compuesto por tres líneas. La primera contiene el número N de símbolos que tiene la tabla de codificación. La segunda línea contiene N números correspondientes a los códigos de cada símbolo. Se garantiza que no hay números repetidos y que ninguno de ellos tiene ceros.
La tercera línea de cada caso de prueba tendrá el mensaje cifrado (una sucesión de entre 1 y 1.000 dígitos) codificado con la tabla anterior. En caso de tener ceros, éstos nunca estarán al principio ni al final del mensaje.
Salida
Para cada caso de prueba se escribirá en una línea independiente el número de mensajes que pueden dar el texto cifrado dado. Como puede haber muchos, se dará el resultado módulo 1.000.000.007.
Entrada de ejemplo
3 1 2 22 1221 3 1 2 22 12021 3 1 2 22 12321 0
Salida de ejemplo
2 1 0