수열 구간의 $\textrm{mex}$를 해당 구간에 나타나지 않는 가장 작은 자연수로 정의하고, 수열의 가치를 $\textrm{mex}\geq k$인 구간의 개수로 정의합니다.

$m$보다 작은 $n$개의 자연수와 구간 $[l,r]$이 주어집니다. $f(k)$를 $n$개의 수로 구성된 수열의 모든 재배열 중 수열 가치의 최댓값이라고 할 때, 모든 $k\in [l,r]$에 대하여 $f(k)$를 구하십시오.

$a_i$를 숫자 $i$가 나타나는 횟수라고 할 때, 모든 $i < m$에 대하여 $a_i\in \{X,X+1\}$을 만족하는 양의 정수 $X$가 존재함이 보장됩니다.

입력

입력 데이터의 양을 줄이기 위해 다음과 같은 방식을 사용합니다.

첫 번째 줄에 네 개의 정수 $m, l, r, X$가 주어집니다.

두 번째 줄에 길이가 $m$인 $01$ 문자열이 주어집니다. $i$번째 위치가 $1$이면 숫자 $i-1$의 등장 횟수는 $X+1$이고, $0$이면 등장 횟수는 $X$입니다.

입력을 통해 $n=mX+S$를 도출할 수 있으며, 여기서 $S$는 $01$ 문자열에 포함된 $1$의 개수입니다.

출력

출력 데이터의 양을 줄이기 위해 $ans=\displaystyle{\bigoplus_{i=l}^r} (233^i f(i) \bmod 998244353)$으로 정의합니다. 여기서 $\displaystyle\bigoplus$은 비트 단위 XOR 연산을 의미하며, 한 줄에 정수 $ans$를 출력하십시오.

예제

입력 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

제한

• 서브태스크 1 (5점): $n,m\leq 9$
• 서브태스크 2 (15점): $n,m\leq 200$
• 서브태스크 3 (15점): $n,m\leq 5\times 10^3$
• 서브태스크 4 (5점): $m\leq 2,l=0,r=1$
• 서브태스크 5 (10점): $m\leq 10^6,l=m,r=m$
• 서브태스크 6 (10점): $m\leq 10^6,X=1,s_i=0$
• 서브태스크 7 (15점): $m\leq 10^6,r-l+1\leq 10^4$
• 서브태스크 8 (15점): $m\leq 2\times 10^6$
• 서브태스크 9 (10점): 특별한 제한 없음

모든 데이터에 대하여 $n\leq 10^9,m\leq 10^7,0\leq l\leq r\leq m,X\geq 1$을 만족합니다.