RoAlgo Contest #10 | subsiruri

Task

You are given a string $a$ of $k$ distinct letters, consisting of the first $k$ letters of the alphabet, and a string $b$ of $n$ letters, which contains only letters from the first $k$ letters of the alphabet.

There are $q$ queries of the form $l \ r$, such that $1 \leq l \leq r \leq n$, to which you must respond with the number of sequences $(i_1, i_2, ..., i_k)$ that exist such that $l \leq i_1 < i_2 < \dots < i_k \leq r$ and $b_{i_j} = a_j$ for any $1 \leq j \leq k$. Since this number can be very large, only the remainder of this number divided by $998\ 244\ 353$ is required.

Input data

The first line contains two integers, $k$ and $n$. The next line contains a string of $k$ distinct letters. The third line contains a string of $n$ letters. The fourth line contains a single integer, $q$. The following $q$ lines contain two integers $l_i$ and $r_i$, representing the data for the $i$-th query.

Output data

On the $i$-th of the $q$ lines, there will be a single integer, the answer to the $i$-th query.

Constraints and clarifications

• $1 \leq n, q \leq 10^5$
• $1 \leq k \leq \min(n, 26)$

Example

stdin

2 12
ab
abababababab
3
3 8
2 5
6 11

stdout

6
1
3

Explanation

For the first query, the subsequence is ababab, and ab appears $6$ times: ABabab, AbaBab, AbabaB, abABab, abAbaB, ababAB.

For the second query, the subsequence is baba, and ab appears only once: bABa.

For the third query, the subsequence is bababa, and ab appears $3$ times: bABaba, bAbaBa, babABa.