Los organizadores de la UCPC están decorando el salón de la competencia con una larga guirnalda de lámparas con forma de letras. La guirnalda forma una cadena de longitud compuesta por letras latinas mayúsculas: la -ésima lámpara muestra la letra s_i. Cada lámpara debe encenderse en uno de tres colores: azul, amarillo o blanco.
Por supuesto, la palabra favorita de los organizadores es UCPC. Una ocurrencia de la palabra UCPC en la guirnalda es una elección de cuatro lámparas en las posiciones i_1 < i_2 < i_3 < i_4 que muestran las letras U, C, P, C respectivamente (las lámparas elegidas no tienen por qué ser adyacentes). La coloración de una ocurrencia es la secuencia de colores de las lámparas i_1, i_2, i_3, i_4 exactamente en ese orden.
Una coloración de toda la guirnalda se llama consistente si todas las ocurrencias de la palabra UCPC tienen la misma coloración. En otras palabras, sin importar qué ocurrencia de la palabra UCPC lea un espectador en la guirnalda, siempre verá la misma secuencia de colores. En particular, si UCPC no aparece en absoluto en la guirnalda, entonces cualquier coloración es consistente.
Cuente la cantidad de coloraciones consistentes de la guirnalda. Dos coloraciones se consideran diferentes si al menos una lámpara tiene colores distintos en ellas. Como la respuesta puede ser grande, imprímala módulo .
Los organizadores están considerando varias guirnaldas, y hay que responder esta pregunta para cada una de ellas.
La primera línea contiene un entero (1 \le t \le 10^6) — la cantidad de guirnaldas.
Cada una de las siguientes líneas contiene una cadena (1 \le |s| \le 10^6, donde es la longitud de la cadena ) — la guirnalda. Se garantiza que la guirnalda consta de letras latinas mayúsculas.
La longitud total de todas las cadenas no supera 10^6.
Para cada guirnalda, imprima en una línea separada un único entero — la cantidad de sus coloraciones consistentes módulo .
Ejemplo 1
En la primera guirnalda del ejemplo, la palabra UCPC aparece cuatro veces, en las posiciones (1,2,3,4), (1,2,3,6), (1,2,5,6) y (1,4,5,6). La lámpara es la segunda letra de la última ocurrencia y la cuarta letra de la primera, por lo que ambas letras C de la palabra deben tener el mismo color. Por lo tanto, todas las lámparas con la letra C comparten un color común, y ambas lámparas con la letra P comparten un color común. Junto con el color de la lámpara , esto da 3^3 = 27 coloraciones consistentes.
En la segunda guirnalda del ejemplo, ninguna lámpara puede ser simultáneamente la segunda y la cuarta letra de una ocurrencia, por lo que las dos letras C de la palabra pueden tener colores diferentes: las lámparas comparten un color común, las lámparas — un color común, las lámparas — un color común y las lámparas — un color común, lo que da 3^4 = 81 coloraciones.
En la tercera guirnalda del ejemplo, la palabra UCPC no aparece en absoluto, por lo que las 3^3 = 27 coloraciones son consistentes.