The $\textrm{mex}$ of a sequence interval is defined as the smallest non-negative integer that does not appear in the interval. The value of a sequence is defined as the number of its intervals whose $\textrm{mex} \geq k$.

Given $n$ non-negative integers less than $m$ and an interval $[l, r]$, let $f(k)$ be the maximum value of a sequence among all permutations of the $n$ given numbers. For each $k \in [l, r]$, find $f(k)$.

Let $a_i$ denote the number of occurrences of the integer $i$. It is guaranteed that there exists a positive integer $X$ such that $\forall i < m, a_i \in \{X, X+1\}$.

Input

Due to the potentially large value of $n$, the input is provided as follows:

The first line contains four integers $m, l, r, X$.

The second line contains a binary string of length $m$. If the $i$-th character is $1$, the number of occurrences of $i-1$ is $X+1$; otherwise, the number of occurrences is $X$.

From the input, one can derive $n = mX + S$, where $S$ is the number of $1$s in the binary string.

Output

To reduce the output size, let $ans = \displaystyle{\bigoplus_{i=l}^r} (233^i f(i) \bmod 998244353)$, where $\displaystyle\bigoplus$ denotes the bitwise XOR operation. Output a single integer $ans$.

Examples

Input 1

2 0 1 2
10

Output 1

3034

Note

In the sequence given in the example, there are $3$ zeros and $2$ ones. For any permutation, $f(0) = 15$. For the permutation $\textrm{01010}$, $f(1)$ reaches its maximum value of $13$. The answer is: $$ \displaystyle (233^0\times 15\bmod 998244353)\oplus(233^1\times 13\bmod 998244353)=3034 $$

Input 2

14 1 14 13
10110101110101

Output 2

379883349

Subtasks

• 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): No special restrictions.

For all data, $n \leq 10^9, m \leq 10^7, 0 \leq l \leq r \leq m, X \geq 1$.