定義一個數列區間的 $\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$ 的 $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$。

數據範圍

• Subtask 1（5 points）：$n, m \leq 9$。
• Subtask 2（15 points）：$n, m \leq 200$。
• Subtask 3（15 points）：$n, m \leq 5 \times 10^3$。
• Subtask 4（5 points）：$m \leq 2, l=0, r=1$。
• Subtask 5（10 points）：$m \leq 10^6, l=m, r=m$。
• Subtask 6（10 points）：$m \leq 10^6, X=1, s_i=0$。
• Subtask 7（15 points）：$m \leq 10^6, r-l+1 \leq 10^4$。
• Subtask 8（15 points）：$m \leq 2 \times 10^6$。
• Subtask 9（10 points）：無特殊限制。

對於所有數據，滿足 $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$ 個 $0$ 和 $2$ 個 $1$，任意排列 $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