题目描述

给定一个长度为 $n$、字符集为 K,D 的字符串 $s$。保证所有测试点中，字符串 $s$ 均存在特殊性质限制，详见「数据范围」。

对 $s$ 的一个长度为 $m$ 的子串

考虑它的一个标号 $c_1,c_2,\ldots,c_m$，满足：

• 对所有 $1\le i\le m$，有 $1\le c_i\le n$，且 $c_i\in\mathbb Z$；
• 二元组 $(t_i,c_i)$ 两两不同。也就是说，若 $i\ne j$ 且 $t_i=t_j$，则 $c_i\ne c_j$。

有一个小人，从位置 $1$ 游行到位置 $m$，初始有无穷的金币。当访问到第 $i$ 个位置时：

• 若 $t_i$ 为 K，他将领取一把类型为 $c_i$ 的钥匙；
• 若 $t_i$ 为 D，他需要开一扇类型为 $c_i$ 的门，也就是需要手里有类型为 $c_i$ 的钥匙。若有该类型钥匙，则可以直接通过；否则需要求救大神，花费一个金币。

定义合法标号 $c_{1\sim m}$ 的代价为最少需要花费的金币数。

记 $f_{\min}(t_{1\sim m})$ 为对所有合法标号 $c_{1\sim m}$，其代价的最小值。可以证明，至少存在一个合法标号方案。小人将能取得 $f_{\min}(t_{1\sim m})$ 的合法标号数量记为 $f(t_{1\sim m})$。

现在有 $q$ 次询问。第 $i$ 次询问给出一个区间 $[l_i,r_i]$，请你求出

对 $998244353$ 取模后的结果。

输入格式

从文件 keys.in 中读入数据。

本题包含多组测试数据。

输入第一行包含两个非负整数 $c,T$，分别表示测试点编号与测试数据组数。$c=0$ 表示该测试点为样例。

接下来依次输入每组测试数据。对于每组测试数据：

• 第一行两个正整数 $n,q$；
• 第二行一个长度为 $n$ 的字符串 $s$；
• 接下来 $q$ 行，每行两个整数 $l_i,r_i$，表示一次询问。

输出格式

输出到文件 keys.out 中。

对于每组测试数据，输出 $q$ 行。第 $i$ 行输出一个非负整数，表示对应询问的答案，对 $998244353$ 取模。

样例 1 输入

0 1
4 3
KKDD
1 3
3 4
1 4

样例 1 输出

24
12
24

样例 1 解释

第二组询问的子串只有门没有钥匙，所以不管怎样标号，小人都需要求救大神两次，因此总方案数是 $4\times 3=12$。

第一组询问中，一种标号方式是 $(c_1,c_2,c_3)=(1,2,3)$，需要求救一次；但它不是最优的，因为例如 $(c_1,c_2,c_3)=(1,2,2)$ 时不需要求救。

附加样例

• 样例 2：见选手目录下的 keys/keys2.in 与 keys/keys2.ans，满足测试点 4 的约束条件。
• 样例 3：见选手目录下的 keys/keys3.in 与 keys/keys3.ans，满足测试点 5 的约束条件。
• 样例 4：见选手目录下的 keys/keys4.in 与 keys/keys4.ans，满足测试点 12、14 的约束条件。

数据范围

对于每组测试数据，均有：

• $1\le T\le 3$；
• $1\le n\le 3\times 10^5$，$1\le q\le 5\times 10^5$；
• $1\le l_i\le r_i\le n$；
• 对所有 $1\le i\le n$，$s_i$ 为 K、D 之一。

特殊性质如下：

• 特殊性质 A：奇数编号测试点满足：对所有 $1\le i\le q$，若 $l_i<r_i$，则 $f_{\min}(s_{l_i\sim r_i})=0$。
• 特殊性质 B：保证 $s_i\ne s_{i+1}$。
• 特殊性质 C：保证 $s$ 在 $2^n$ 个合法字符串中等概率随机生成。

请注意：所有测试点均存在特殊性质。本题输入输出量较大，建议使用较快的输入输出方式。

难度评定

• 估计难度：NOI Day2 T1 ~ T2 难度，CF 约 2900 ~ 3100。
• 评定理由：最小代价本质上与序列中 K 与之后 D 的最大匹配有关，但本题还要求统计所有达到最小代价的合法标号数，并支持大规模区间询问。计数部分需要组合分析，查询部分需要结合特殊性质 A/B/C 设计不同策略，整体明显高于普通括号匹配或区间计数题。