数列の区間の $\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$ を満たします。