题目描述

整数 $N,\ X$ が与えられます。$0$ 以上 $X$ 以下のすべての整数 $k$ に対し、 $k$ に以下の操作を繰り返すことによって次に $k$ に戻るまでの操作回数 (戻らない場合 $0$) を足し合わせた値を $998244353$ で割ったあまりを求めてください。

• 現在の整数が奇数なら、$1$ を引いて $2$ で割る。そうでなければ、$2$ で割って $2^{N-1}$ を足す。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $X$

输出格式

$0$ 以上 $X$ 以下のすべての整数に対し、 操作を繰り返すことによってもとの整数に戻るまでの操作回数 (戻らない場合 $0$) を足し合わせた値を $998244353$ で割ったあまりを出力せよ。

题目大意

题目描述

现在给你一个整数$N$和一个二进制数$X$，对$0 \sim X$之间的每个整数$K$在返回到其原始值之前，需要执行多少次下面的操作：

如果$K$是奇数

$K=(K-1) \div 2$

如果$K$是偶数

$K=(K \div 2)+2^{N-1}$

输入格式

第一行输入一个整数$N$，第二行输入一个$N$位的整数$X$。

输出格式

一个整数，表示$0 \sim X$之间的每个整数$K$在返回到其原始值之前，需要执行的操作次数的总和。

由于答案可能过大,请对最终答案$mod \text{ 998244353}$。

说明/提示

• $1 \le N \le 2 \times10^5$
• $0 \le X \le 2^N$
• $X$是一个长度为$N$的二进制数($X$的数位不足$N$时用前导$0$补齐)
• 所有数字都是整数

例如,$K = 3$时，操作为：1，0，4，6，7，3，所以$K=3$时答案是$6$。

3
111

40

6
110101

616

30
001110011011011101010111011100

549320998

提示

制約

• $1\ \leq\ N\ \leq\ 2\times\ 10^5$
• $0\ \leq\ X\ <\ 2^N$
• $X$ は $2$ 進表記でちょうど $N$ 桁与えられる ($X$ が $N$ 桁より少ない場合、leading zero をつけて与えられる。)
• 入力はすべて整数である

Sample Explanation 1

例えば、$k=3$ のとき、操作によって整数は $1,0,4,6,7,3$ と順に変化します。したがって、$k=3$ のときの操作回数は $6$ です。