Divine Loyalty Test

The Almighty wants to test the loyalty of His followers using a twist of fate. He has prepared a binary string $a$ of length $n$, representing His predetermined choices for $n$ questions. Each question has two options: the "more radical" option (denoted by 1) and the "more conservative" option (denoted by 0).

He chooses a contiguous block of $k$ questions from $a$, where $k$ is chosen uniformly at random from the range $[l, r]$. Then, a follower answers these $k$ questions by replying with a binary string $b$ of length $k$, where each bit is chosen independently and uniformly (0 or 1).

For a fixed block (with God’s choices $p$ and follower’s answers $q$ of length $k$), we say that $q$ is loyal to $p$ if the following condition holds for every $2 \le i \le k$:

[ \text{if } q_{i-1} = p_{i-1} \text{ then } q_i \ge p_i, \quad \text{else } q_i \le p_i. ]

Note that for the first question, loyalty is always granted.

Your task is to calculate the probability that a follower is loyal. In other words, first a length $k$ (with $l\le k\le r$) is chosen uniformly, then a contiguous substring of $a$ of length $k$ is chosen uniformly, and finally a binary string $b$ of length $k$ is chosen uniformly (each bit is 0 or 1 with equal probability). Compute the probability that $b$ is loyal to the chosen substring of $a$. Since the answer may be a rational number, output it modulo (998244353) (using modular inverses when necessary).

All formulas must be written in ( \LaTeX ) format. For example, the condition above is given by

[ \forall; 2 \le i \le k,\quad \text{if } q_{i-1}=p_{i-1}\text{ then } q_i\ge p_i\text{, otherwise } q_i\le p_i. ]

It is guaranteed that the input is such that the answer is well–defined.

inputFormat

The first line contains three integers (n), (l), and (r) (with (1 \le l \le r \le n)). The second line contains a binary string (a) of length (n).

outputFormat

Output a single integer, the probability (modulo (998244353)) that a randomly chosen follower (as described) is loyal.

sample

4 1 2
1010

748683265