$\textrm{mex}$ отрезка последовательности определяется как наименьшее натуральное число, не входящее в этот отрезок. Ценностью последовательности называется количество её отрезков, для которых $\textrm{mex} \geq k$.
Даны $n$ натуральных чисел, каждое из которых меньше $m$, и отрезок $[l, r]$. Пусть $f(k)$ — максимальное значение ценности среди всех возможных перестановок данной последовательности из $n$ чисел. Для каждого $k \in [l, r]$ требуется найти $f(k)$.
Пусть $a_i$ — количество вхождений числа $i$ в последовательность. Гарантируется, что существует такое натуральное число $X$, что для всех $i < m$ выполняется $a_i \in \{X, X+1\}$.
Формат входных данных
Поскольку $n$ может быть очень большим, для сокращения объема входных данных используется следующий формат:
В первой строке заданы четыре целых числа $m, l, r, X$.
Во второй строке задана бинарная строка длины $m$. Если на $i$-й позиции стоит $1$, то число $i-1$ встречается $X+1$ раз, в противном случае — $X$ раз.
На основе этих данных можно вычислить $n = mX + S$, где $S$ — количество единиц в бинарной строке.
Формат выходных данных
Для сокращения объема вывода вычислите $ans = \displaystyle{\bigoplus_{i=l}^r} (233^i f(i) \bmod 998244353)$, где $\displaystyle\bigoplus$ обозначает операцию побитового исключающего ИЛИ (XOR). Выведите одно целое число $ans$.
Ограничения
- Subtask 1 (5 баллов): $n, m \leq 9$.
- Subtask 2 (15 баллов): $n, m \leq 200$.
- Subtask 3 (15 баллов): $n, m \leq 5 \times 10^3$.
- Subtask 4 (5 баллов): $m \leq 2, l=0, r=1$.
- Subtask 5 (10 баллов): $m \leq 10^6, l=m, r=m$.
- Subtask 6 (10 баллов): $m \leq 10^6, X=1, s_i=0$.
- Subtask 7 (15 баллов): $m \leq 10^6, r-l+1 \leq 10^4$.
- Subtask 8 (15 баллов): $m \leq 2 \times 10^6$.
- Subtask 9 (10 баллов): без дополнительных ограничений.
Для всех данных выполняются условия: $n \leq 10^9, m \leq 10^7, 0 \leq l \leq r \leq m, X \geq 1$.
Примеры
Входные данные 1
2 0 1 2 10
Выходные данные 1
3034
Примечание
В последовательности из примера содержится $3$ нуля и $2$ единицы. Для любой перестановки $f(0) = 15$. При перестановке $\textrm{01010}$ значение $f(1)$ достигает максимума, равного $13$. Ответ вычисляется как: $$ \displaystyle (233^0 \times 15 \bmod 998244353) \oplus (233^1 \times 13 \bmod 998244353) = 3034 $$
Входные данные 2
14 1 14 13 10110101110101
Выходные данные 2
379883349