9466: Zero

Given a string $\textstyle s$ of length $\textstyle n$, which only contains the characters $\textstyle 0$, $\textstyle 1$, and $\textstyle ?$. For any interval $\textstyle [l, r]$ ($\textstyle 1 \leq l \leq r \leq n$), if the substring from the $\textstyle l$\-th to the $\textstyle r$\-th character is entirely composed of $\textstyle 1$s, its value is $\textstyle (r - l + 1)^k$; otherwise, its value is $\textstyle 0$. The value of the string is defined as the sum of the values of all intervals. Assuming that every $\textstyle ?$ in $\textstyle s$ is independently replaced with $\textstyle 0$ or $\textstyle 1$ with equal probability, what is the expected value of the string? Output the result modulo $\textstyle 998,244,353$.

The first line contains two integers $\textstyle n$ and $\textstyle k$ ($\textstyle 1 \leq n \leq 10^5, 1 \leq k \leq 30$), representing the length of the string and the parameter for calculating the value, respectively. The second line contains a string $\textstyle s$ of length $\textstyle n$, which consists only of the characters $\textstyle 0$, $\textstyle 1$, and $\textstyle ?$.

Output a single integer, the expected value of the string modulo $\textstyle 998,244,353$. Formally, let $\textstyle M = 998\,244\,353$. It can be shown that the answer can be expressed as an irreducible fraction $\textstyle \frac{p}{q}$, where $\textstyle p$ and $\textstyle q$ are integers and $\textstyle q \not \equiv 0 \pmod{M}$. Output the integer equal to $\textstyle p \cdot q^{-1} \bmod M$. In other words, output such an integer $\textstyle x$ that $\textstyle 0 \leq x < M$ and $\textstyle x \cdot q \equiv p \pmod{M}$.