AT_xmascon21_c Count Me

[problemUrl]: https://atcoder.jp/contests/xmascon21/tasks/xmascon21_c 文字 `0`, `1`, `?` からなる長さ $ N $ の文字列 $ S $ が与えられる．文字列の $ N\ +\ 1 $ 個組 $ (t_0,\ t_1,\ \ldots,\ t_N) $ であって以下の条件をすべて満たすものの個数を $ 998244353 $ で割った余りを求めよ： - $ t_0 $ は空文字列である． - 各 $ i\ =\ 0,\ 1,\ \ldots,\ N\ -\ 1 $ に対し，$ t_{i+1} $ は，$ t_i $ に `0` または `1` を $ 1 $ 個いずれかの場所に挿入して得られる文字列である． - $ t_N $ は，$ S $ に現れる `?` をそれぞれ `0` または `1` で置き換えて得られる文字列である．

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

個数を $ 998244353 $ で割った余りを出力せよ．

### 制約 - $ 1\ \le\ N\ \le\ 250\,000 $． - $ S $ は `0`, `1`, `?` からなる長さ $ N $ の文字列である． ### 部分点 - $ N\ \le\ 5\,000 $ を満たすデータセットに正解した場合は，$ 10 $ 点が与えられる． - 追加制約のないデータセットに正解した場合は，上記とは別に $ 90 $ 点が与えられる． ### Sample Explanation 1 条件を満たす組 $ (t_0,\ t_1,\ t_2,\ t_3) $ は以下の $ 8 $ 個である： - $ t_0 $ が空文字列，$ t_1 $ が `0`，$ t_2 $ が `00`，$ t_3 $ が `010`． - $ t_0 $ が空文字列，$ t_1 $ が `0`，$ t_2 $ が `01`，$ t_3 $ が `010`． - $ t_0 $ が空文字列，$ t_1 $ が `0`，$ t_2 $ が `01`，$ t_3 $ が `011`． - $ t_0 $ が空文字列，$ t_1 $ が `0`，$ t_2 $ が `10`，$ t_3 $ が `010`． - $ t_0 $ が空文字列，$ t_1 $ が `1`，$ t_2 $ が `01`，$ t_3 $ が `010`． - $ t_0 $ が空文字列，$ t_1 $ が `1`，$ t_2 $ が `01`，$ t_3 $ が `011`． - $ t_0 $ が空文字列，$ t_1 $ が `1`，$ t_2 $ が `10`，$ t_3 $ が `010`． - $ t_0 $ が空文字列，$ t_1 $ が `1`，$ t_2 $ が `11`，$ t_3 $ が `011`．