Cuatro escalones#13107

Cuatro escalones

2,5 segundos
256 megabytes

Se te da una cadena de longitud formada por los caracteres 0, 1, 2, 3 y ?. Cada carácter ? debe ser reemplazado por uno de los dígitos , , , (distintas apariciones pueden reemplazarse por dígitos distintos).

Para una cadena de dígitos u_1 u_2 \ldots u_n, un ascenso es una cuádrupla de índices i < j < k < l tal que u_i = 0, u_j = 1, u_k = 2 y u_l = 3. Los índices no tienen por qué ser consecutivos.

Cuenta los reemplazos para los cuales el número de ascensos en la cadena resultante es divisible entre . Dos reemplazos son diferentes si algún carácter ? se reemplaza por dígitos distintos en ellos. Como la respuesta puede ser grande, imprímela módulo .

Entrada

La primera línea contiene un único entero (1 \le t \le 10^5) — el número de casos de prueba.

Cada una de las siguientes líneas contiene una cadena no vacía formada por los caracteres 0, 1, 2, 3 y ?.

La longitud total de todas las cadenas no supera 5 \cdot 10^5.

Salida

Para cada caso de prueba imprime un entero — el número de reemplazos para los cuales el número de ascensos es divisible entre , módulo .

Ejemplos

Ejemplo 1

Loading
Loading

Nota

En el primer caso de prueba no contiene caracteres ? y tiene exactamente un ascenso. El número no es divisible entre , por lo que la respuesta es .

En el segundo caso de prueba contiene un carácter ?. Si se reemplaza por , o , la cadena resultante no tiene ascensos, y es divisible entre . Si se reemplaza por , la cadena resultante es 0123, que tiene un ascenso. Por lo tanto, la respuesta es .

En el tercer caso de prueba cada ascenso usa una de las dos apariciones de cada dígito, por lo que hay 2 \cdot 2 \cdot 2 \cdot 2 = 16 ascensos, y es divisible entre . No hay caracteres ?, así que la respuesta es .

En el cuarto caso de prueba consta de cuatro caracteres ?, por lo que hay 4^4 = 256 reemplazos. Solo la cadena 0123 tiene un ascenso (exactamente uno), y todas las demás no tienen ninguno, así que la respuesta es .

En el quinto caso de prueba no contiene ascensos.