Definimos el $\textrm{mex}$ de un intervalo de una sucesión como el menor número natural que no aparece en dicho intervalo, y definimos el valor de una sucesión como la cantidad de intervalos en ella tales que $\textrm{mex} \geq k$.
Dados $n$ números naturales menores que $m$ y un intervalo $[l, r]$, sea $f(k)$ el valor máximo del valor de la sucesión entre todas las posibles permutaciones de los $n$ números. Para cada $k \in [l, r]$, calcule $f(k)$.
Sea $a_i$ la cantidad de veces que aparece el número $i$. Se garantiza que existe un entero positivo $X$ tal que $\forall i < m, a_i \in \{X, X+1\}$.
Formato de entrada
Debido a que $n$ puede ser muy grande, se utiliza el siguiente formato para reducir la cantidad de datos de entrada:
La primera línea contiene cuatro enteros $m, l, r, X$.
La segunda línea contiene una cadena binaria de longitud $m$. Si la posición $i$ es $1$, entonces el número $i-1$ aparece $X+1$ veces; de lo contrario, aparece $X$ veces.
A partir de la entrada se puede deducir que $n = mX + S$, donde $S$ es la cantidad de unos en la cadena binaria.
Formato de salida
Para reducir la cantidad de salida, sea $ans = \displaystyle{\bigoplus_{i=l}^r} (233^i f(i) \bmod 998244353)$, donde $\displaystyle\bigoplus$ denota la operación OR exclusivo (XOR) a nivel de bits. Imprima una sola línea con el entero $ans$.
Ejemplos
Entrada 1
2 0 1 2 10
Salida 1
3034
Nota
En la sucesión dada en el ejemplo, hay $3$ ceros y $2$ unos. Para cualquier permutación, $f(0) = 15$. Para la permutación $\textrm{01010}$, $f(1)$ alcanza su valor máximo de $13$. La respuesta es: $$ \displaystyle (233^0 \times 15 \bmod 998244353) \oplus (233^1 \times 13 \bmod 998244353) = 3034 $$
Entrada 2
14 1 14 13 10110101110101
Salida 2
379883349
Restricciones
- Subtarea 1 (5 puntos): $n,m\leq 9$.
- Subtarea 2 (15 puntos): $n,m\leq 200$.
- Subtarea 3 (15 puntos): $n,m\leq 5\times 10^3$.
- Subtarea 4 (5 puntos): $m\leq 2,l=0,r=1$.
- Subtarea 5 (10 puntos): $m\leq 10^6,l=m,r=m$.
- Subtarea 6 (10 puntos): $m\leq 10^6,X=1,s_i=0$.
- Subtarea 7 (15 puntos): $m\leq 10^6,r-l+1\leq 10^4$.
- Subtarea 8 (15 puntos): $m\leq 2\times 10^6$.
- Subtarea 9 (10 puntos): Sin restricciones adicionales.
Para todos los datos, se cumple que $n\leq 10^9, m\leq 10^7, 0\leq l\leq r\leq m, X\geq 1$.