Description

The god wants to test whether his believers are loyal, and he decides to use luck as the test.

The god has prepared $n$ questions in advance. Each question has two choices: “relatively radical” and “relatively conservative”. The god has already fixed his own choices.

To test his believers, the god will uniformly choose one from all feasible ways of selecting questions (a feasible way means choosing a consecutive $k$ questions, with $l\leq k\leq r$, where $l,r$ are given). Then the believers will answer each of the $k$ questions in order with either “relatively radical” or “relatively conservative”. The god will judge whether a believer is loyal based on his own choices and that believer’s answers.

The judging rules are:

• This is the first question: no matter what the answer is, the god is willing to believe the believer is loyal.
• This is not the first question: if the believer’s previous answer is the same as the god’s choice, then the god will require them to explore more advanced choices, so the believer’s answer to this question cannot be more conservative than the god’s choice; otherwise, the god will require the believer to obey him, so the believer’s answer to this question cannot be more radical than the god’s choice.

If the believer’s answers satisfy the above requirements, then the believer is loyal.

Now, the god wants to know: if a believer answers each question uniformly at random with “relatively radical” or “relatively conservative”, what is the probability that the believer is loyal? He asks you this question through Fiona, and requires you to output the result modulo $998244353$. If you cannot answer in time, you will lose the god’s trust.

Simplified statement:

Given a binary string $a$ of length $n$ and $l,r(l\leq r)$.

For two binary strings $p,q$ of the same length $k$, we say that $q$ is “loyal” to $p$ if and only if $p$ and $q$ satisfy:

• For any $1<i\leq k$, if $q_{i-1}=p_{i-1}$, then $q_i\geq p_i$, otherwise $q_i\leq p_i$.

You need to compute the probability that: first, uniformly choose a substring of $a$ whose length $k$ satisfies $l\leq k\leq r$, and then uniformly choose a binary string $b$ of length $k$, such that $b$ is “loyal” to that substring. Output the result modulo $998244353$.

Input Format

The first line contains three integers $n,l,r$, as described above.

The second line contains a string of length $n$, representing $a$. It is guaranteed that the string contains only characters 0 and 1.

Output Format

Output one integer in one line, representing the answer.

5 2 3
01101

338690049

17 4 13
10101110100101101

512357021

Hint

Explanation for Sample 1:

We use $\left[l,r\right]$ to denote the interval where the chosen substring lies.

• Choose $\left[1,2\right]$. The substring is 01, with length $2$. There are $3$ binary strings that are “loyal” to this substring, so the probability is $\dfrac{3}{4}$.

• Choose $\left[1,3\right]$. The substring is 011, with length $3$. There are $4$ binary strings that are “loyal” to this substring, so the probability is $\dfrac{1}{2}$.

• Choose $\left[2,3\right]$. The probability is $\dfrac{3}{4}$.

• Choose $\left[2,4\right]$. The probability is $\dfrac{5}{8}$.

• Choose $\left[3,4\right]$. The probability is $\dfrac{3}{4}$.

• Choose $\left[3,5\right]$. The probability is $\dfrac{1}{2}$.

• Choose $\left[4,5\right]$. The probability is $\dfrac{3}{4}$.

So the result is $\dfrac{\dfrac{3}{4}+\dfrac{1}{2}+\dfrac{3}{4}+\dfrac{5}{8}+\dfrac{3}{4}+\dfrac{1}{2}+\dfrac{3}{4}}{7}=\dfrac{37}{56}$, which is $338690049$ modulo $998244353$.

This problem uses bundled testdata.

• Subtask 1 ( $1\%$ ): $n=1$.
• Subtask 2 ( $13\%$ ): $n\leq100$.
• Subtask 3 ( $3\%$ ): Guaranteed that $\forall1\leq i\leq n,a_i=0$.
• Subtask 4 ( $3\%$ ): Guaranteed that $\forall1\leq i\leq n,a_i=1$.
• Subtask 5 ( $20\%$ ): $n\leq10^3$.
• Subtask 6 ( $15\%$ ): $l=r$.
• Subtask 7 ( $20\%$ ): $n\leq 5\times 10^5$.
• Subtask 8 ( $25\%$ ): No special constraints.

Constraints: for all testdata, $1\leq n\leq5\times 10^6,1\leq l\leq r\leq n$。

Translated by ChatGPT 5