A sequence of letters is called a word. A sequence of letters is considered special if all the characters within the word are unique (There are no duplicate letters).

Given a sequence of letters ~S~ and ~Q~ queries, for each query, determine the number of possible Special Sequences that can be created using all the unique characters between index ~L~ and ~R~ (inclusive) of string ~S~.

Input Specification

The first line will consist of two integers ~|S|~ ~(1 \le |S| \le 10^5)~ and ~Q~ ~(1 \le Q \le 10^5)~, the length of string ~S~ and the number of queries.
The next line will contain a single string ~S~ of length ~|S|~ consisting of uppercase characters between A to Z.
The last ~Q~ lines will consist of 2 integers, ~L_i~ and ~R_i~ ~(1 \le L_i, R_i, \le |S|)~, representing a query using characters between ~L~ and ~R~ (inclusive) of string ~S~.

Output Specification

For each query ~Q~, output the number of possible Special Sequences using characters between the ~L~th and ~R~th character of string ~S~ ~mod~ ~100000007~

Subtasks

Subtask 1 [10%]:

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

Subtask 2 [20%]:

• ~1 \le Q \le 10~

Subtask 3 [70%]:

• No further constraints

Sample Input 1

3 1
XYZ
1 3

Sample Output 1

6

Explanation for Sample Output 1

There are a total of 6 unique Special Sequences using characters between indices 1 and 3:
XYZ, XZY, YXZ, YZX, ZXY, ZYX.

Sample Input 2

9 4
SSSUUUSSS
1 3
3 4
4 6
1 9

Sample Output 2

1
2
1
2

Explanation of Sample Output 2

The only possible Special Sequence using characters between indices 1 and 3 is S.
The two characters between 3 and 4 are S and U, the only possible Special Sequences are SU and US
The only possible Special Sequence using characters between indices 4 and 6 is U.
The two characters unique characters between 1 and 10 are S and U, the only possible Special Sequences are SU and US

Sample Input 3

26 1
ABCDEFGHIJKLMNOPQRSTUVWXYZ
1 26

Sample Output 3

49626704

Explanation for Sample Output 3

Make sure to output your answer ~mod~ ~100000007~.