KurbyDoo has recently become obsessed with strings and poses the following question

Given a string of length ~S~ and ~Q~ queries, output how many permutations there are of the substring between index ~L~ and ~R~ (inclusive)

Can you help KurbyDoo answer his question?

Input Specification

The first line will contain two integers ~|S|~ ~(1 \le |S| \le 10^5)~ length of the string, and ~Q~ ~(1 \le Q \le 10^5)~ the number of queries.
The next line will contain a single string of length ~|S|~. The next ~Q~ lines will contain two integers ~L_i~ and ~R_i~ indicating the range of the ~i~th query.

Output Specification

Output ~Q~ lines, each containing the number of possible string permutations ~mod~ ~100000007~ using the characters between ~L_i~ and ~R_i~ where ~i~ represents the ~i~th query.

Subtasks

Subtask 1 [2/12]:

• ~1 \le |S| \le 10~
• ~Q = 1~

Subtask 2 [5/12]:

• ~1 \le Q \le 10~

Subtask 3 [5/12]:

• No further constraints

Sample Input 1

6 3
BANANA
3 5
1 4
2 6

Sample Output 1

3
12
10

Explanation for Sample Input 1

There are 3 total permutations of the string between 3 and 5: ANN, NAN, NNA.
There are 12 total permutations of the string between 1 and 4: BAAN, BANA, BNAA, ABAN, ABNA, NBAA, AABN, ANBA, NABA, AANB, ANAB, NAAB.
There are 10 total permutations of the string between 2 and 6: AAANN, AANAN, AANNA, ANAAN, ANANA, ANNAA, NAAAN, NAANA, NANAA, NNAAA.

Sample Input 2

12 1
ABCDEFGHIJKL
1 12

Sample Output 2

79001572

Explanation for Sample Output 2

Make sure to output the number of permutations ~mod~ ~100000007~.