subsiruri

Time limit: 0.5s Memory limit: 1024MB Input: Output:

Task

You are given a string aa of kk distinct letters, consisting of the first kk letters of the alphabet, and a string bb of nn letters, which contains only letters from the first kk letters of the alphabet.

There are qq queries of the form l rl \ r, such that 1lrn1 \leq l \leq r \leq n, to which you must respond with the number of sequences (i1,i2,...,ik)(i_1, i_2, ..., i_k) that exist such that li1<i2<<ikrl \leq i_1 < i_2 < \dots < i_k \leq r and bij=ajb_{i_j} = a_j for any 1jk1 \leq j \leq k. Since this number can be very large, only the remainder of this number divided by 998 244 353998\ 244\ 353 is required.

Input data

The first line contains two integers, kk and nn. The next line contains a string of kk distinct letters. The third line contains a string of nn letters. The fourth line contains a single integer, qq. The following qq lines contain two integers lil_i and rir_i, representing the data for the ii-th query.

Output data

On the ii-th of the qq lines, there will be a single integer, the answer to the ii-th query.

Constraints and clarifications

  • 1n,q1051 \leq n, q \leq 10^5
  • 1kmin(n,26)1 \leq k \leq \min(n, 26)
# Points Constraints
0 0 Example
1 10 n,q100,k10n, q \leq 100, k \leq 10
2 12 n,q1 000,k10n, q \leq 1\ 000, k \leq 10
3 5 k=1k = 1
4 23 k5k \leq 5
5 50 No additional constraints

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 66 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 33 times: bABaba, bAbaBa, babABa.

Log in or sign up to be able to send submissions!