配点 : $800$ 点

問題文

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

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

制約

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

入力

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

$N$

$X$

出力

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

3
111

40

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

6
110101

616

30
001110011011011101010111011100

549320998