Tanmay and his PROness

0

0 votes
Hard
Problem

Argusoft is having problem in designing algorithm for a client under given constraints. So, they hired Tanmay (also known as tanmay273) as he is well known PRO-coder. He solved it in very less time . As He loves to give Good challenges to his juniors, now he wants you to solve the same problem .Here is the problem :

you will be given two string A and B. and he will give you Q queries. each query will consist of two integers L and R, you have to tell how many subsequences of A[L:R] will be equal to B. here A[L:R] denotes substring of A which starts at index L and ends at index R. since answer can be large so you need to tell answer modulo 109+7.

Input
first line will consist of two integer N and M, representing the length of A and B respectively. it will be followed by String A and B. next line will contain Q representing number of queries, next Q line will contain two integers L and R.

Output
for each query output the number of subsequences modulo 109+7

Constraints

1 <= N ,Q <= 250000
1 <= L <= R <= N
1 <= M <= 5

both the strings A and B will be consist of only lower case letters.

Sample Input
10 3
tanmayproo
pro
5
1 10
1 5
1 9
5 9
1 8
Sample Output
2
0
1
1
0
Time Limit: 2
Memory Limit: 256
Source Limit:
Editor Image

?