A Ribbon for Tomorrow

Problema

Se da una cadena binaria s de longitud n. Se puede aplicar la siguiente operación cualquier cantidad de veces, incluyendo cero:

• elegir dos índices l y r tales que 1 ≤ l ≤ r ≤ n y, en la cadena actual, s[l] = s[r];
• invertir el orden de los caracteres de la subcadena s[l..r].

Determina cuántas cadenas binarias distintas pueden obtenerse a partir de s. Devuelve la respuesta módulo 998244353.

Entrada

La primera línea contiene el número de casos de prueba t.

Para cada caso de prueba:

1. una línea contiene el entero n;
2. la siguiente línea contiene una cadena binaria s de longitud n.

Salida

Para cada caso de prueba, imprime un entero: el número de cadenas binarias distintas alcanzables desde s, módulo 998244353.

Rangos / restricciones

• 1 ≤ t ≤ 10^4.
• 1 ≤ n ≤ 10^6.
• s contiene únicamente 0 y 1 y tiene longitud n.
• La suma de n sobre todos los casos de prueba no excede 10^6.
• Límite de tiempo: 2 segundos.
• Límite de memoria: 256 MB.

Observaciones

La condición s[l] = s[r] se evalúa sobre la cadena en su estado actual, después de todas las operaciones realizadas previamente.