P7495 异位坍缩

>自然的法则隐藏在黑暗之中。 月光之下，菲欧娜和一群与她有着同样信仰的信徒们聚集在一起，等待着他们所信仰的神明降临。 「神明大人，我们愿意永远追随您。」

神明想要测试他的信徒们是否忠诚，他决定用运气来进行测试。 神明事先准备了 $n$ 个问题，每个问题都有两种选择：**「相对激进的」** 和 **「相对保守的」**。神明已经定好了自己的选择。 为了考验他的信徒们，神明会在所有可行的问题选择方式中**等概率选出一种**（可行的选择方式指选出**连续的** $k$ 个问题，满足 $l\leq k\leq r$，其中 $l,r$ 给定），然后信徒们会依次对这 $k$ 个问题中的每个问题回答「相对激进的」或「相对保守的」。神明会根据自己的选择以及某个信徒的回答来判定这名信徒是否忠诚。 神明的判定方式是这样的： + 这是第一个问题：无论回答如何，神明都愿意相信这名信徒是忠诚的。 + 这不是第一个问题：如果这名信徒的上一个回答与神明的选择相同，那么神明会需要他去对更先进的选择进行探索，因此这名信徒在这个问题的回答**不能比神明的选择更保守**；否则，神明会要求这名信徒服从于自己，在这个问题的回答**不能比神明的选择更激进**。 如果这名信徒的回答满足上述要求，那么这名信徒就是忠诚的。 现在，神明想要知道，如果信徒对每个问题都会**等概率回答「相对激进的」或「相对保守的」**，那么一名信徒有多大的概率会是忠诚的。他通过菲欧娜向你提出了这个问题，并要求你将结果对 $998244353$ 取模。如果你无法及时回答出，那么你就会失去神明的信任。 ------------ #### 简要题意： 给定一个长度为 $n$ 的 01 串 $a$ 以及 $l,r(l\leq r)$。 对于两个长度均为 $k$ 的 01 串 $p,q$，我们认为 $q$ 对于 $p$ 是「忠诚的」，当且仅当 $p$ 和 $q$ 满足如下要求： + 对于任意 $1

第一行三个整数 $n,l,r$，意义如上。 第二行有一个长度为 $n$ 的字符串，表示 $a$。保证字符串只含字符 `0` 和 `1`。

一行一个整数，表示结果。

#### 样例一解释： 我们用 $\left[l,r\right]$ 表示所选择的子串所在区间。 + 选择 $\left[1,2\right]$，子串为 `01`，长度为 $2$，有 $3$ 个 01 串对这个子串是「忠诚的」，概率为 $\dfrac{3}{4}$。 + 选择 $\left[1,3\right]$，子串为 `011`，长度为 $3$，有 $4$ 个 01 串对这个子串是「忠诚的」，概率为 $\dfrac{1}{2}$。 + 选择 $\left[2,3\right]$，概率为 $\dfrac{3}{4}$。 + 选择 $\left[2,4\right]$，概率为 $\dfrac{5}{8}$。 + 选择 $\left[3,4\right]$，概率为 $\dfrac{3}{4}$。 + 选择 $\left[3,5\right]$，概率为 $\dfrac{1}{2}$。 + 选择 $\left[4,5\right]$，概率为 $\dfrac{3}{4}$。 结果为 $\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}$，取模意义下为 $338690049$。 ------------ **本题采用捆绑测试** + Subtask 1 ( $1\%$ )：$n=1$。 + Subtask 2 ( $13\%$ )：$n\leq100$。 + Subtask 3 ( $3\%$ )：保证 $\forall1\leq i\leq n,a_i=0$。 + Subtask 4 ( $3\%$ )：保证 $\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\%$ )：无特殊限制。 对于所有数据，$1\leq n\leq5\times 10^6,1\leq l\leq r\leq n$。