AT_scpc2026_div1_f Connecting Chips

#### 表示言語 / / > FuriosaAIは今年、第2世代AIアクセラレータ「RNGD」の量産を正式に発表した。RNGDは言語モデルおよびマルチモーダルモデルの処理に特化した製品であり、低消費電力でありながら強力な演算性能を提供する。 RNGDチップの量産ニュースを聞いたソロヒューは、RNGDチップを $ N $ 個注文した。ソロヒューのコンピュータには、チップを1つずつ差し込めるスロットが $ (N+2M) $ 個並んでおり、そのうち $ 2M $ 個のスロットには、SチップとCチップがそれぞれ $ M $ 個ずつ差し込まれている。SチップとCチップは、特異なことに、1つのSチップと1つのCチップを互いに配線で接続しなければ正しく動作しない。 ソロヒューは、注文したRNGDチップが届くまで、SチップとCチップを配線で接続することにした。空いているスロットの上を配線が通りすぎると、後でチップを挿しにくくなるため、2つのチップを配線で接続する際は、配線が**最大1つの**空いているスロットの上を通るように接続しなければならない。すでに挿されているSチップとCチップを抜いて再配置することはできない。 スロットの状態を表す文字列 $ T $ が与えられる。ソロヒューのコンピュータに挿されている $ M $ 組のチップを配線で接続する、互いに異なる方法の数を求めよう。 ある2つのチップが、ある方法では互いに配線で接続されているが、別の方法ではそうでない場合、その2つの方法は互いに異なるとする。

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

$ M $ 組のチップを配線で接続する方法の数を $ 998\,244\,353 $ で割った余りを出力する。

### Constraints - $ 1 \le N \le 10\,000 $ - $ 1 \le M \le 10\,000 $ - 文字列 $ T $ は、`E` が $ N $ 個、`S` が $ M $ 個、`C` が $ M $ 個からなる文字列である。 - $ T $ の $ i $ 番目の文字は、 $ i $ 番目のスロットに挿入されているチップの種類を表し、`E`はスロットが空であることを、`S`はSチップが挿入されていることを、`C`はCチップが挿入されていることを意味する - 入力される値はすべて整数