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 10⁹+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 10⁹+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.