EOJ Monthly 2021.7 Sponsored by TuSimple

C. 渡渡鸟

单点时限: 1.0 sec

内存限制: 512 MB

蟹老板正在给梦幻庄园引进新的动物表演项目。为了在全世界各地的动物园中脱颖而出,蟹老板不惜花费重金,向罗德岛购买了大量的渡渡鸟蛋。等这些渡渡鸟孵化、长大之后,蟹老板的梦幻庄园就将成为全世界唯一一个拥有渡渡鸟的动物园。

这些渡渡鸟蛋有两个品种,一种是黑壳的,一种是白壳的。为了给这些鸟准备舒适的成长环境,蟹老板为它们修建了豪华鸟舍。鸟舍一共有 $n$ 间,从左往右依次编号为 $1,2,\dots,n$。每间鸟舍中安放一只鸟蛋。在先进的自动孵化设备的帮助下,没过几天,初生的渡渡鸟们就破壳而出了。

可是蟹老板没有料到的是,一个鸟蛋竟然可以孵化出多只渡渡鸟,甚至可以孵化出多只不同品种的渡渡鸟!这就使得原本宽敞的鸟舍显得有点拥挤了。蟹老板从罗德岛处得知,渡渡鸟共有 $26$ 个品种,可以使用小写字母 a-z 编号。而且,所有同种类的蛋的孵化模式是完全一致的,也就是说,同种类的蛋孵化出的渡渡鸟的种类都是相同的,甚至孵化的先后顺序都是一样的。先孵化出来的鸟会自发地站到鸟舍的左边,这样依次排成一列。由于一个鸟蛋的空间是有限的,所以一个鸟蛋理论是最多可以孵化出 $k$ 只渡渡鸟,且每个鸟蛋至少孵出一只小鸟。

例如,如果黑色的蛋可以依次孵化出 ataz 四只渡渡鸟,白色的蛋可以依次孵化出 ata 三只渡渡鸟,且蟹老板的鸟舍中分别放置了 黑|白|黑|黑 的鸟蛋,那么孵化后各个鸟舍的情况为 ataz|ata|ataz|ataz

有一天,蟹老板视察鸟舍时发现,有些连续区间中的渡渡鸟竟然是完全相同的,这是多么奇妙的事情!他很想知道原因,但是早已忘记了黑白两色蛋的孵化模式。所以蟹老板会告诉你,一开始他往鸟舍中分别放置了哪些鸟蛋,以及 $Q$ 次询问,每次询问他会告诉你,$[l_0,r_0]$ 鸟舍中的鸟和 $[l_1,r_1]$ 鸟舍中的鸟序列是完全相同的,想请你计算一下,有多少种孵化模式可以导致这样的效果。

【简短题意】
给定一个长度为 $n$ 的 01 串 $S$,所有 0 将会替换为小写字母串 $A$,所有 1 将会替换为串 $B$($1 \le |A|,|B| \le k$)。$Q$ 次询问,每次给定 $S$ 的两个子串,已知这两个子串按如上规则替换后完全相同,请问有多少种串 $A,B$ 满足要求。

输入格式

第一行输入三个整数 $n,k,Q$($1\le n,k,Q \le 5\times 10^5$),分别表示鸟舍的数量,一只鸟蛋最多孵化出的渡渡鸟数量和询问个数。

第二行输入一个 01 字符串 $S$,0 表示对应位置上是黑色的鸟蛋,1 表示对应位置上是白色的鸟蛋。

接着 $Q$ 行,每行输入四个整数 $l_0,r_0,l_1,r_1$,表示一组询问,$s=S_{l_0,r_0},t=S_{l_1,r_1}$,下标从 1 开始标号,表示 $[l_0,r_0]$ 鸟舍中的鸟和 $[l_1,r_1]$ 鸟舍中的鸟序列是完全相同的。

每次询问都是独立且互不影响的。

输出格式

$Q$ 行,每行一个数表示,有多少种孵化模式可以使得 $[l_0,r_0]$ 鸟舍中的鸟和 $[l_1,r_1]$ 鸟舍中的鸟序列是完全相同的,对 $998~244~353$ 取模。

样例

Input
4 2 2
0011
1 2 3 3
1 2 2 3
Output
26
702

提示

【样例 1 解释】
对于第一组询问,黑白两色蛋的孵化模式为 (a, aa)、(b, bb)、…,共 $26$ 种。
以 (a, aa) 为例,因为询问的两个区间分别为 黑黑,因为一个黑蛋可以孵化出一个 a,一个白蛋可以依次孵化出 aa,所以 黑黑 最终孵化为 aa 最终也孵化为 aa,两个区间的鸟序列完全相同。

【样例 2 解释】
对于第二组询问,黑色蛋和白色蛋的孵化模式完全相等,共 $702$ 种。