题目描述

解密需要两个非空字符串 $A,B$ 作为密码。两个字符串的长度均不超过 $k$，并且只包含小写英文字母。

通过研究，你发现破译的关键在于两个 01 字符串 $s,t$。将 $s,t$ 中的每个字符按以下规则替换：

• 将每个 0 替换为字符串 $A$；
• 将每个 1 替换为字符串 $B$。

替换完成后，由 $s$ 得到的字符串必须与由 $t$ 得到的字符串完全相同。

然而，你无法确定真正的 $s,t$，只知道它们都是字符串 $S$ 的子串。

为了估算破译时间，你进行了 $Q$ 次猜测。每次给出两个子串 $s',t'$，请计算：若它们就是真正的 $s,t$，可能的有序密码对 $(A,B)$ 一共有多少种。

输入格式

第一行输入三个整数 $n,k,Q$，分别表示字符串 $S$ 的长度、密码字符串的长度上限，以及询问数量。

第二行输入一个长度为 $n$ 的 01 字符串 $S$。

接下来 $Q$ 行，每行输入四个整数 $l_0,r_0,l_1,r_1$，表示

字符串下标从 $1$ 开始。

输出格式

输出 $Q$ 行。每行输出对应询问的答案，并对 $998244353$ 取模。

样例输入 1

4 2 2
0011
1 2 3 3
1 2 2 3

样例输出 1

26
702

样例解释

对于第一组询问，可行的 $(A,B)$ 为

共 $26$ 组。

对于第二组询问，必须满足 $A=B$。长度不超过 $2$ 的非空小写字母串共有

种，因此答案为 $702$。

数据范围与约定

• 对于测试点 1～2，保证 $k=1$，且 $n,Q\le 10$；
• 对于测试点 3～4，保证 $k,n,Q\le 10$；
• 对于测试点 5～6，保证 $s'$ 首尾翻转后等于 $t'$；
• 对于测试点 7～8，保证 $Q=1$；
• 对于全部测试点，保证