AT_scpc2026_div1_f Connecting Chips

FuriosaAI 官方宣布其第二代 AI 加速器 RNGD 芯片于今年实现量产。RNGD 是一款专为处理语言模型和多模态模型设计的产品，既能提供强大的计算性能，又能极低功耗运行。 在得知 RNGD 芯片量产的消息后，Sorohue 订购了 $N$ 枚 RNGD 芯片。Sorohue 的计算机有 $N+2M$ 个插槽排成一排，每个插槽可以插入一枚芯片。其中，有 $2M$ 个插槽已分别被 $M$ 枚 S 芯片和 $M$ 枚 C 芯片占用。特别的是，S 芯片和 C 芯片要能正常工作，必须一一通过导线连接成 $M$ 对。 在等待 RNGD 芯片到货期间，Sorohue 决定先将 S 芯片和 C 芯片两两配对，用导线连接。为了避免导线跨越过多的空插槽，导致日后插入芯片困难，每对芯片用导线连接时，导线通过的空插槽 **最多只能有一个**。已经插入的 S 芯片和 C 芯片不允许移动或重新安置。 给定一个字符串 $T$，表示插槽的状态，求用导线将 Sorohue 计算机中的 $M$ 对芯片两两配对的不同方案数。 如果有两种方案，某对芯片是否将被导线连接不同，则这两种方案被认为是不同的。

输入为标准输入，格式如下： $N$ $M$ $T$

输出用导线连接 $M$ 对芯片的方案数，结果对 $998\,244\,353$ 取模。

### 数据范围 - $1 \le N \le 10\,000$ - $1 \le M \le 10\,000$ - $T$ 是一个只包含 $N$ 个 `E`、$M$ 个 `S` 和 $M$ 个 `C` 的字符串。 - 第 $i$ 个字符表示第 $i$ 个插槽的状态，`E` 表示空槽，`S` 表示 S 芯片，`C` 表示 C 芯片。 - 所有输入均为整数。 由 ChatGPT 5 翻译