You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

串联（$\texttt{link}$）

【题目描述】

小 D 有写着 $0\sim n-1$ 的珠子各 $k$ 颗，某天他又捡到了一些珠子（每种珠子 $\le 1$ 个）。

他想把这些珠子串联成一条链，小 D 心里有一个数 $x$，如果这条链中的某一个段（一个区间）中写着 $0\sim x-1$ 的珠子都出现过，那么他认为这个区间是美丽的。

定义 $f(x)$ 表示所有把珠子串成链的方案中，美丽区间数的最大值。

他不确定 $x$ 具体的值，因此他请你帮他求出 $f(l)\sim f(r)$。

【输入格式】

从 $\texttt{link.in}$ 中读入数据。

第一行四个整数 $n,l,r,k$。

第二行一个长度为 $n$ 的 01 串 $S$，$S$ 的第 $i$ 个位置为 $1$ 说明他又捡到了一颗写着 $i-1$ 的珠子。

【输出格式】

输出到 $\texttt{link.out}$ 中。

一行一个整数表示 $\bigoplus_{i=l}^r(f(i)\times 233^i\bmod 998244353)$ 的值，其中 $\oplus$ 表示二进制异或。

【样例 1 输入】

2 0 1 2
10

【样例 1 输出】

3034

【样例 1 解释】

$f(0)=15,f(1)=13$，链形如 $0,1,0,1,0$ 时取到最大值。

【样例 2 输入】

14 1 14 13
10111101010101

【样例 2 输出】

1062272474

【样例 3】

见下发文件中的 $\texttt{link3.in}$ 与 $\texttt{link3.ans}$。

该样例满足子任务 $8$ 的限制

【数据范围】

设 $m$ 表示珠子总数（$m=nk+\sum_{i=1}^n S_i$）。

对于所有的测试数据有：$n\le 10^7,m\le 10^9,0\le l\le r\le m,k\ge 1$。