問題文

2N 枚のカードがあります。 i~(1 \leq i \leq 2N) 番目のカードには、整数 i が書かれています。

千咲さんと月乃瀬さんは、これらのカードを使って次のようなゲームをすることにしました。

1. カードをよくシャッフルし、N 枚ずつ取ってお互いの最初の手札とする。
2. ゲームは N ラウンドからなる。各ラウンドでは、2 人のプレイヤーは手札の中で最も小さい数が書かれたカードを選び、見せ合う。見せたカードに書かれた数の大きいほうが、そのラウンドの勝者になる。見せたカードはお互いに手札から取り除き、それ以降のラウンドでは考慮しない。

千咲さんと月乃瀬さんは、このゲームを 1 回プレイしました。

ゲームの結果が 0 と 1 のみからなる長さ N の文字列 S として与えられます。 任意の整数 i\ (1 \leq i \leq N) について、S_i が 1 のとき、 千咲さんがゲームの i 回目のラウンドの勝者になったことを、S_i が 0 のとき、そうでないことを意味します。

このようなゲームの結果を与える千咲さんの最初の手札として、ありえるものは何種類あるでしょうか？ 答えはとても大きくなることがあるため、998244353 で割った余りを出力してください。

制約

• 1 \leq N \leq 10^5
• S は 0 と 1 のみからなる長さ N の文字列である。

入力例 1

2
01

出力例 1

1

千咲さんの最初の手札に 1 と 4 が、月乃瀬さんの最初の手札に 2 と 3 が書かれたカードがある場合を考えます。このとき、

• 1 回目のラウンドでは、千咲さんは 1 が書かれたカードを、月乃瀬さんは 2 が書かれたカードをお互いに見せ、月乃瀬さんがラウンドの勝者になります。
• 2 回目のラウンドでは、千咲さんは 4 が書かれたカードを、月乃瀬さんは 3 が書かれたカードをお互いに見せ、千咲さんがラウンドの勝者になります。

よって、千咲さんのこの最初の手札は、与えられたゲーム結果を満たします。

入力例 2

15
111110001011100

出力例 2

2100