AT_arc193_b [ARC193B] Broken Wheel

正整数 $ N $ と、`0` と `1` のみからなる長さ $ N $ の文字列 $ s_0s_1\ldots s_{N-1} $ が与えられます。 $ 0, 1, 2, \ldots, N $ と番号づけられた $ (N+1) $ 個の頂点と、下記の辺からなる単純無向グラフ $ G $ を考えます。 - 各 $ i = 0, 1, \ldots, N-1 $ について、頂点 $ i $ と頂点 $ (i+1)\bmod N $ を結ぶ無向辺がある。 - 各 $ i = 0, 1, \ldots, N-1 $ について、 $ s_i = $ `1` のとき、かつ、そのときに限り、頂点 $ i $ と頂点 $ N $ を結ぶ無向辺がある。 - 上記の他に辺はない。 さらに、 $ G $ の各辺を任意に向きづけして有向グラフ $ G' $ を作ります。すなわち、 $ G $ の各無向辺 $ \lbrace u, v \rbrace $ を、 $ u $ から $ v $ への有向辺 $ (u, v) $ と $ v $ から $ u $ への有向辺 $ (v, u) $ のどちらか一方で置き換えます。 各 $ i = 0, 1, \ldots, N $ について、 $ G' $ における頂点 $ i $ の入次数を $ d_i $ とおくとき、 得られる数列 $ (d_0, d_1, \ldots, d_N) $ としてありえるものの個数を $ 998244353 $ で割った余りを出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ s_0s_1\ldots s_{N-1} $

答えを出力せよ。

### Sample Explanation 1 $ G $ は $ \lbrace 0, 1 \rbrace, \lbrace 0, 2 \rbrace, \lbrace 1, 2 \rbrace, \lbrace 1, 3 \rbrace $ の $ 4 $ 本の無向辺を持ちます。 例えば、それぞれの辺を $ 0 \to 1 $ 、 $ 2 \to 0 $ 、 $ 2 \to 1 $ 、 $ 1 \to 3 $ と向きづけた場合、 $ (d_0, d_1, d_2, d_3) = (1, 2, 0, 1) $ が得られます。 $ (d_0, d_1, d_2, d_3) $ として得られるものは、 $ (0, 1, 2, 1) $ , $ (0, 2, 1, 1) $ , $ (0, 2, 2, 0) $ , $ (0, 3, 1, 0) $ , $ (1, 0, 2, 1) $ , $ (1, 1, 1, 1) $ , $ (1, 1, 2, 0) $ , $ (1, 2, 0, 1) $ , $ (1, 2, 1, 0) $ , $ (1, 3, 0, 0) $ , $ (2, 0, 1, 1) $ , $ (2, 1, 0, 1) $ , $ (2, 1, 1, 0) $ , $ (2, 2, 0, 0) $ の $ 14 $ 個です。 ### Constraints - $ 3 \leq N \leq 10^6 $ - $ N $ は整数 - $ s_i $ は `0` または `1`