Genética Bovina.


Submit solution

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

Author:
Problem type
Allowed languages
C, C#, C++, Java, Pascal, Python, VB

Tras secuenciar los genomas de sus vacas, el granjero John ha pasado a la edición genómica. Como sabemos, un genoma puede representarse mediante una cadena formada por As, Cs, Gs y Ts. La longitud máxima de un genoma considerado por el granjero John es de 10^5.

El granjero John comienza con un único genoma y lo edita realizando los siguientes pasos:

  1. Dividir el genoma entre cada dos caracteres iguales consecutivos.
  2. Invertir cada una de las subcadenas resultantes.
  3. Concatenar las subcadenas invertidas en el mismo orden.

Por ejemplo, si GJ comenzara con el genoma AGGCTTT, realizaría los siguientes pasos:

  1. Dividir entre las Gs y Ts consecutivas para obtener AG | GCT | T | T.
  2. Invertir cada subcadena para obtener GA | TCG | T | T.
  3. Concatenar las subcadenas para obtener GATCGTT.

Desgraciadamente, después de editar el genoma, el ordenador de GJ se estropeó y perdió la secuencia del genoma con el que había empezado. Además, algunas partes del genoma editado se han dañado, lo que significa que han sido sustituidas por signos de interrogación.

Dada la secuencia del genoma editado, ayuda a GJ a determinar el número de posibilidades del genoma original, módulo 10^9 + 7.

Entrada

Una cadena no vacía donde cada carácter es uno de A, G, C, T, o ?.

Salida

El número de posibles genomas originales módulo 10^9 + 7.

Ejemplo #1 de Entrada

?

Ejemplo #1 de Salida

4

El signo de interrogación puede ser A, G, C o T.

Ejemplo #2 de Entrada

GAT?GTT

Ejemplo #2 de Salida

3

Hay dos posibles genomas originales aparte de AGGCTTT, que fue descrito anteriormente.

AGGATTT \rarr AG | GAT | T | T \rarr GA | TAG | T | T \rarr GATAGTT

TAGGTTT \rarr TAG | GT | T | T \rarr GAT | TG | T | GATTGTT.

Restricciones

\bull En los casos de prueba 1-4, el genoma tiene una longitud máxima de 10.

\bull En los casos de prueba 5-11, el genoma tiene una longitud máxima de 10^2.

\bull En los casos de prueba 12-20, no hay restricciones adicionales.


Comments

There are no comments at the moment.