题目描述

定义一个数列区间的 $\textrm{mex}$ 为区间中最小的没有出现过的自然数，定义一个数列的价值为其中 $\textrm{mex}\geq k$ 的区间数量。

给定 $n$ 个小于 $m$ 的自然数和一个区间 $[l,r]$，令 $f(k)$ 表示 $n$ 个数构成的数列所有重排列中数列价值的最大值，对于每一个 $k\in [l,r]$，求出 $f(k)$。

令 $a_i$ 表示数字 $i$ 出现的次数，保证存在正整数 $X$，使得 $\forall 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^if(i)\bmod 998244353)$，其中 $\displaystyle\bigoplus$ 表示二进制下的按位异或，输出一行一个整数 $ans$。

样例 1

输入

2 0 1 2
10

输出

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

输出

379883349

数据范围与提示

• 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$