Zero
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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 1s, 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}.
示例1

输入

复制 
10 3
01??110???

输出

复制 
873463930