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 ~A~s, ~C~s, ~G~s y ~T~s. 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.