题目描述

斐波那契串的定义为：给定 $S_1, S_2$，对于任意 $i > 2$，满足

其中“$+$”的定义是把第二个字符串接到第一个字符串的后方（即 string 类型的加法操作）。

定义两个字符串等价为它们的最小循环表示法相同。
最小循环表示法的定义为：每次把串 $T$ 的第一个字符移到最后一个位置，形成的所有字符串中字典序最小的那个。

例如，bab 的所有循环表示为 bab、abb、bba，其中字典序最小的是 abb。

给定 $S_1, S_2$，有 $Q$ 组询问。
每次给定一个整数 $id$ 和一个长度为 $m_i$ 的字符串 $T$，询问 $T$ 在 $S_{id}$ 中的出现次数（即 $S_{id}$ 中有多少个子串和 $T$ 等价）。

输入格式

• 第一行和第二行分别为两个字符串 $S_1, S_2$。
• 第三行为一个整数 $Q$，表示询问个数。
• 接下来 $Q$ 行，每行先读入一个整数 $id$，接下来一个字符串表示 $T$。

输出格式

• 一共 $Q$ 行，每行输出一个整数，表示 $T$ 在 $S_{id}$ 中的出现次数。
• 输出答案对 $998244353$ 取模。

Samples

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

1
0
3
0
1

Limitation

1s, 1024KiB for each test case.