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.

FuriosaAI 公司今年正式宣布其第二代人工智能加速器 RNGD 进入量产阶段。RNGD 是一款专为处理语言模型与多模态模型而设计的产品，在提供强大计算性能的同时，功耗极低。

得知 RNGD 芯片开始量产的消息后，Sorohue 订购了 $N$ 块 RNGD 芯片。Sorohue 的计算机拥有 $(N+2M)$ 个插槽，排成一列，每个插槽可容纳一块芯片。其中，$2M$ 个插槽已被占据：$M$ 个插槽安装了 S 芯片，另外 $M$ 个插槽安装了 C 芯片。特别地，每块 S 芯片必须通过导线与恰好一块 C 芯片相连，才能正常工作。

Sorohue 决定在订购的 RNGD 芯片到货前，先用导线将已安装的 S 芯片与 C 芯片连接起来。由于过多的导线跨越空插槽会妨碍后续芯片的插入，因此在用导线连接两块芯片时，该导线最多只能跨越一个空插槽。已插入的 S 芯片和 C 芯片不可移除或重新排列。

给定一个字符串 $T$，表示当前插槽的状态。请计算将 Sorohue 计算机中已安装的 $M$ 对芯片（即 $M$ 块 S 芯片与 $M$ 块 C 芯片）用导线连接起来的不同方式数目。

若在一种连接方式中，某两块芯片被导线连接，而在另一种方式中未被连接，则这两种方式被视为不同。

The input is given from Standard Input in the following format:

$N$ $M$
$T$

输入从标准输入中按以下格式给出：

$N$ $M$
$T$

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

输出用导线连接 $M$ 对芯片的方案数，对 $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.

表示语言

/ /

约束条件

• $1 \le N \le 10\,000$
• $1 \le M \le 10\,000$
• 设 $T$ 是一个由 $N$ 个 E、$M$ 个 S 和 $M$ 个 C 组成的字符串。
  • $T$ 的第 $i$ 个字符表示插入第 $i$ 个插槽的芯片类型，其中 E 表示空插槽，S 表示 S 型芯片，C 表示 C 型芯片。
• 所有输入值均为整数。