D - Maximin Game /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200

問題文

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

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

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

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

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

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

制約

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

入力

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

N
S

出力

千咲さんの最初の手札として、ありえるものの種類数を 998244353 で割った余りを出力せよ。


入力例 1

2
01

出力例 1

1

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

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

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


入力例 2

15
111110001011100

出力例 2

2100