数列の区間の $\textrm{mex}$ を、その区間に含まれない最小の自然数と定義します。また、数列の価値を、$\textrm{mex} \geq k$ を満たす区間の数と定義します。
$m$ 未満の自然数からなる $n$ 個の数と区間 $[l, r]$ が与えられます。$f(k)$ を、$n$ 個の数から構成される数列のすべての並び替えのうち、数列の価値が最大となる値とします。すべての $k \in [l, r]$ に対して $f(k)$ を求めてください。
$a_i$ を数字 $i$ が出現する回数とします。正の整数 $X$ が存在し、すべての $i < m$ に対して $a_i \in \{X, X+1\}$ が成り立つことが保証されています。
入力
$n$ が非常に大きくなる可能性があるため、入力量を削減するために以下の形式をとります。
1 行目に 4 つの整数 $m, l, r, X$ が与えられます。
2 行目に長さ $m$ の $01$ 文字列が与えられます。この文字列の $i$ 番目の文字が $1$ である場合、数字 $i-1$ の出現回数は $X+1$ であり、そうでない場合は $X$ です。
入力から $n = mX + S$ が導かれます。ここで $S$ は $01$ 文字列に含まれる $1$ の個数です。
出力
出力量を削減するため、$ans = \displaystyle{\bigoplus_{i=l}^r} (233^i f(i) \bmod 998244353)$ とします。ここで $\displaystyle\bigoplus$ はビット単位の排他的論理和を表します。$ans$ を 1 行で出力してください。
入出力例
入力 1
2 0 1 2 10
出力 1
3034
注記
与えられた数列には $0$ が $3$ 個、$1$ が $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
制約
- 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$ を満たします。