C 字符串（string）

TIME:1S MEMORY:1024M

【问题描述】

​ 小 $\text{X}$ 在学完树的同构后，想字符串同构如何处理？

​ 定义两个字符串同构当且仅当它们的最小表示法相同。循环同构是当字符串 $S$ 中可以选定一个位置 $i$ 满足$S[i\cdots n]+S[1\cdots i-1]=T$ 则称 $S$ 与 $T$ 循环同构。字符串 $S$ 的最小表示为与 $S$ 循环同构的所有字符串中字典序最小的字符串。

​ 现在给定字符串 $S_1,S_2$。对于 $\forall i>2$，定义 $S_i=S_{i-1}+S_{i-2}$，加法表示字符串拼接。

​ 有 $Q$ 组询问，每次给定一个数 $id$ 和一个字符串 $T$，询问 $S_{id}$ 有多少个子串和 $T$ 同构。答案对$998244353$ 取模。

【输入格式】

​ 从文件 $string.in$ 中读入数据。

​ 第一行一个字符串表示 $S_1$。

​ 第二行一个字符串表示 $S_2$。

​ 第三行一个整数 $Q$，表示询问个数。

​ 接下来 $Q$ 行，每行一个整数 $id$ 和一个字符串 $T$，表示一次询问。

【输出格式】

​ 输出到文件 $string.out$ 中。

​ 对每组询问输出一行一个整数，表示答案。

【样例输入1】

a
b
5
1 a
1 b
5 ab
5 c
5 abba

【样例输出1】

1
0
3
0
1

【样例2】

​ 见选手目录下的 $string/string2.in$ 与 $string/string2.ans$。

【数据范围及约定】

​ 令 $M$ 表示所有 $T$ 的长度和。所有字符串均由小写字母组成。