AT_kupc2019_d Maximin Game

[problemUrl]: https://atcoder.jp/contests/kupc2019/tasks/kupc2019_d $ 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 $ で割った余りを出力してください。

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

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

### 制約 - $ 1\ \leq\ N\ \leq\ 10^5 $ - $ S $ は `0` と `1` のみからなる長さ $ N $ の文字列である。 ### Sample Explanation 1 千咲さんの最初の手札に $ 1 $ と $ 4 $ が、月乃瀬さんの最初の手札に $ 2 $ と $ 3 $ が書かれたカードがある場合を考えます。このとき、 - $ 1 $ 回目のラウンドでは、千咲さんは $ 1 $ が書かれたカードを、月乃瀬さんは $ 2 $ が書かれたカードをお互いに見せ、月乃瀬さんがラウンドの勝者になります。 - $ 2 $ 回目のラウンドでは、千咲さんは $ 4 $ が書かれたカードを、月乃瀬さんは $ 3 $ が書かれたカードをお互いに見せ、千咲さんがラウンドの勝者になります。 よって、千咲さんのこの最初の手札は、与えられたゲーム結果を満たします。