AT_arc196_c [ARC196C] Strongly Connected

$ 2N $ 頂点 $ 2N-1 $ 辺の有向グラフがあります。 頂点には $ 1, 2, \ldots, 2N $ の番号がついており、 $ i $ 番目の辺は頂点 $ i $ から頂点 $ i+1 $ に向かう有向辺です。 $ N $ 個の `W` と $ N $ 個の `B` からなる長さ $ 2N $ の文字列 $ S=S_1S_2\ldots S_{2N} $ が与えられます。 頂点 $ i $ は $ S_i $ が `W` のとき白、`B` のとき黒で塗られています。 あなたは以下の一連の操作を行います。 - $ 2N $ 個の頂点を白の頂点と黒の頂点 $ 1 $ つずつからなる $ N $ 組のペアに分ける。 - 各ペアについて白の頂点から黒の頂点に向かう辺を追加する。 操作において頂点を $ N $ 組のペアに分ける方法のうち、最終的に得られるグラフが強連結となるような方法の数を $ 998244353 $ で割ったあまりを出力してください。 強連結とは？有向グラフが**強連結**であるとは、グラフに含まれる任意の頂点から任意の頂点にいくつかの辺をたどって移動可能であることを言います。

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

操作において頂点を $ N $ 組のペアに分ける方法のうち、最終的に得られるグラフが強連結となるような方法の数を $ 998244353 $ で割ったあまりを出力せよ。

### Sample Explanation 1 頂点 $ 2,4 $ は白色で、頂点 $ 1,3 $ は黒色で塗られています。 頂点 $ u $ から頂点 $ v $ を向かう辺を辺 $ (u,v) $ で表すことにします。 頂点 $ (2,1), (4,3) $ のようにペア分けをした場合、最終的なグラフに存在する辺は辺 $ (1,2), (2,3), (3,4), (2,1), (4,3) $ となります。このとき、例えば頂点 $ 3 $ から頂点 $ 1 $ にいくつかの辺をたどって移動することはできないので、このグラフは強連結ではありません。 頂点 $ (2,3), (4,1) $ のようにペア分けをした場合、最終的なグラフに存在する辺は， $ (1,2), (2,3), (3,4), (2,3), (4,1) $ となります。このグラフは強連結です。 よって条件を満たすペア分けの方法の数は $ 1 $ 通りです。 ### Sample Explanation 2 どのようにペア分けを行っても条件を満たすことができません。 ### Constraints - $ 1 \le N \le 2\times 10^5 $ - $ S $ は $ N $ 個の `W` と $ N $ 個の `B` からなる長さ $ 2N $ の文字列 - $ N $ は整数