题目描述

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

输入格式

The first line contains two integers $n$ and $k$ ($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 $s$ of length $n$, which consists only of the characters $0$, $1$, and $?$.官方中文

输出格式

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