On définit le $\textrm{mex}$ d'un intervalle d'une suite comme le plus petit entier naturel qui n'apparaît pas dans cet intervalle. On définit la valeur d'une suite comme le nombre d'intervalles de cette suite dont le $\textrm{mex} \geq k$.
Étant donné $n$ entiers naturels inférieurs à $m$ et un intervalle $[l, r]$, soit $f(k)$ la valeur maximale parmi toutes les permutations possibles de la suite de $n$ nombres. Pour chaque $k \in [l, r]$, calculez $f(k)$.
Soit $a_i$ le nombre d'occurrences du nombre $i$. On garantit qu'il existe un entier positif $X$ tel que $\forall i < m, a_i \in \{X, X+1\}$.
Entrée
En raison de la taille potentiellement grande de $n$, l'entrée est fournie de la manière suivante :
La première ligne contient quatre entiers $m, l, r, X$.
La deuxième ligne contient une chaîne binaire de longueur $m$. Si le $i$-ème caractère est $1$, alors le nombre $i-1$ apparaît $X+1$ fois, sinon il apparaît $X$ fois.
À partir de ces données, on peut déduire $n = mX + S$, où $S$ est le nombre de $1$ dans la chaîne binaire.
Sortie
Afin de réduire la taille de la sortie, soit $ans = \displaystyle{\bigoplus_{i=l}^r} (233^i f(i) \bmod 998244353)$, où $\displaystyle\bigoplus$ représente l'opération OU exclusif (XOR) au niveau du bit. Affichez un seul entier $ans$.
Exemples
Entrée 1
2 0 1 2 10
Sortie 1
3034
Remarque
Dans la suite donnée par l'exemple, il y a $3$ fois le nombre $0$ et $2$ fois le nombre $1$. Pour toute permutation, $f(0) = 15$. Pour la permutation $\textrm{01010}$, $f(1)$ atteint sa valeur maximale de $13$. La réponse est : $$ \displaystyle (233^0\times 15\bmod 998244353)\oplus(233^1\times 13\bmod 998244353)=3034 $$
Entrée 2
14 1 14 13 10110101110101
Sortie 2
379883349
Contraintes
- Sous-tâche 1 (5 points) : $n, m \leq 9$.
- Sous-tâche 2 (15 points) : $n, m \leq 200$.
- Sous-tâche 3 (15 points) : $n, m \leq 5\times 10^3$.
- Sous-tâche 4 (5 points) : $m \leq 2, l=0, r=1$.
- Sous-tâche 5 (10 points) : $m \leq 10^6, l=m, r=m$.
- Sous-tâche 6 (10 points) : $m \leq 10^6, X=1, s_i=0$.
- Sous-tâche 7 (15 points) : $m \leq 10^6, r-l+1 \leq 10^4$.
- Sous-tâche 8 (15 points) : $m \leq 2\times 10^6$.
- Sous-tâche 9 (10 points) : Aucune contrainte particulière.
Pour toutes les données, on a $n \leq 10^9, m \leq 10^7, 0 \leq l \leq r \leq m, X \geq 1$.