AT_scpc2026_div1_f Connecting Chips

#### 表示言語 / / > FuriosaAI officially announced the mass production of its second-generation AI accelerator, the RNGD, this year. The RNGD is a product specialized for processing language models and multimodal models, delivering powerful computational performance while consuming minimal power. Upon hearing the news of the RNGD chip’s mass production, Sorohue ordered $ N $ RNGD chips. Sorohue’s computer has $ (N+2M) $ slots arranged in a row, each capable of holding a single chip. Of these, $ 2M $ slots are occupied by $ M $ S-chips and $ M $ C-chips, respectively. Uniquely, the S-chips and C-chips require a single S-chip and a single C-chip to be connected via wires in order to function properly. Sorohue decided to connect the S-chips and C-chips with wires until the ordered RNGD chips arrive. Since having too many wires crossing over empty slots makes it difficult to insert chips later, when connecting two chips with a wire, the wire must cross over **at most one** empty slot. It is not possible to remove and rearrange the S-chips and C-chips that are already inserted. A string $ T $ representing the state of the slots is given. Find the number of distinct ways to connect the $ M $ pairs of chips installed in Sorohue’s computer using wires. Two methods are considered distinct if, in one method, two chips are connected by a wire, whereas in the other method they are not.

The input is given from Standard Input in the following format: > $ N $ $ M $ $ T $

Print the number of ways to connect $ M $ pairs of chips with wires, modulo $ 998\,244\,353 $ .

### Constraints - $ 1 \le N \le 10\,000 $ - $ 1 \le M \le 10\,000 $ - Let $ T $ be a string consisting of $ N $ occurrences of `E`, $ M $ occurrences of `S`, and $ M $ occurrences of `C`. - The $ i $ th character of $ T $ represents the type of chip inserted into the $ i $ th slot, where `E` indicates an empty slot, `S` indicates an S-chip, and `C` indicates a C-chip. - All input values are integers.