EOJ Monthly 2021.7 Sponsored by TuSimple

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

这些渡渡鸟蛋有两个品种，一种是黑壳的，一种是白壳的。为了给这些鸟准备舒适的成长环境，蟹老板为它们修建了豪华鸟舍。鸟舍一共有 $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$ 满足要求。