$\textrm{mex}$ przedziału liczbowego definiuje się jako najmniejszą liczbę naturalną, która nie występuje w tym przedziale. Wartość ciągu definiuje się jako liczbę jego przedziałów, dla których $\textrm{mex} \geq k$.

Dany jest ciąg $n$ liczb naturalnych mniejszych od $m$ oraz przedział $[l, r]$. Niech $f(k)$ oznacza maksymalną wartość ciągu spośród wszystkich permutacji $n$ liczb. Dla każdego $k \in [l, r]$ należy wyznaczyć $f(k)$.

Niech $a_i$ oznacza liczbę wystąpień liczby $i$. Gwarantuje się, że istnieje taka liczba całkowita dodatnia $X$, że dla każdego $i < m$ zachodzi $a_i \in \{X, X+1\}$.

Wejście

Ze względu na to, że $n$ może być bardzo duże, dane wejściowe są ograniczone w następujący sposób:

W pierwszym wierszu znajdują się cztery liczby całkowite $m, l, r, X$.

W drugim wierszu znajduje się ciąg binarny o długości $m$. Jeśli na $i$-tej pozycji znajduje się $1$, to liczba $i-1$ występuje $X+1$ razy, w przeciwnym razie występuje $X$ razy.

Na podstawie danych wejściowych można wyznaczyć $n = mX + S$, gdzie $S$ jest liczbą jedynek w ciągu binarnym.

Wyjście

Aby ograniczyć ilość danych wyjściowych, niech $ans = \displaystyle\bigoplus_{i=l}^r (233^i f(i) \bmod 998244353)$, gdzie $\displaystyle\bigoplus$ oznacza operację bitową XOR. Należy wypisać jedną liczbę całkowitą $ans$.

Przykład

Wejście 1

2 0 1 2
10

Wyjście 1

3034

Uwagi

W podanym ciągu występują $3$ zera oraz $2$ jedynki. Dla dowolnej permutacji $f(0) = 15$. Dla permutacji $\textrm{01010}$ wartość $f(1)$ osiąga maksimum równe $13$. Wynik wynosi: $$ \displaystyle (233^0\times 15\bmod 998244353)\oplus(233^1\times 13\bmod 998244353)=3034 $$

Wejście 2

14 1 14 13
10110101110101

Wyjście 2

379883349

Ograniczenia

• Podzadanie 1 (5 punktów): $n, m \leq 9$.
• Podzadanie 2 (15 punktów): $n, m \leq 200$.
• Podzadanie 3 (15 punktów): $n, m \leq 5\times 10^3$.
• Podzadanie 4 (5 punktów): $m \leq 2, l=0, r=1$.
• Podzadanie 5 (10 punktów): $m \leq 10^6, l=m, r=m$.
• Podzadanie 6 (10 punktów): $m \leq 10^6, X=1, s_i=0$.
• Podzadanie 7 (15 punktów): $m \leq 10^6, r-l+1 \leq 10^4$.
• Podzadanie 8 (15 punktów): $m \leq 2\times 10^6$.
• Podzadanie 9 (10 punktów): brak dodatkowych ograniczeń.

Dla wszystkich danych wejściowych spełnione są warunki: $n \leq 10^9, m \leq 10^7, 0 \leq l \leq r \leq m, X \geq 1$.