問題文

整数 N と、0 と 1 のみからなる長さ N の文字列 T が与えられます。 0 と 1 のみからなる、長さ 2N の文字列 S = s_1 s_2 \ldots s_{2N} と T を用いて、Alice と Bob がゲームをします。二人は Alice から始めて、S の全ての文字に印がつくまで交互に以下の操作をします。

• 1 \le i \le 2N を満たす整数 i であって、s_i にまだ印がついていないようなものを選ぶ。その後、
  • Alice の手番であれば、その桁に o の印をつける。
  • Bob の手番であれば、その桁に x の印をつける。

ゲームが終了した時に、o の印がついている桁だけを左から読み、N 文字の文字列として解釈したものが、辞書順で T 以上であれば Alice の勝利、そうでなければ Bob の勝利です。

開始時に用いる文字列 S として考えられるものは 2^{2N} 通りあります。このうち、両者がそれぞれ自身が勝つために最適な戦略をとる場合に、 Alice が勝つようなものの個数を 998244353 で割ったあまりを求めてください。

制約

• N は整数
• 1 \le N\le 2 \times 10^5
• T は 0, 1 のみからなる長さ N の文字列

入力例 1

1
0

出力例 1

4

0 または 1 からなる長さ 2 の全ての文字列が該当します。

入力例 2

1
1

出力例 2

3

01, 10, 11 の 3 つが該当します。

入力例 3

12
011011000111

出力例 3

13225655