DNA Demolition

Four types of bases are found inside a DNA molecule- Adenine (A), Cytosine (C), Guanine (G), and Thymine (T). A DNA molecule can be seen as a string of these bases. For example, the string “ACTAG“ represents a DNA molecule containing bases in the sequence Adenine (A), Cytosine (C), Thymine (T), Adenine (A) again, and finally Guanine (G).

Given a string $s$ consisting of $n$ characters, each of which are either A, C, T or G, you are to output the results of $q$ queries.

Each query specifies two integers $l$ and $r$. You have to find the number of subsequences of the string formed by combining the characters $s[l], s[l+1], s[l+2], …., s[r]$ such that each of these have one or more characters of each base type (i. e. contain at least 1 ‘A’, ‘C’, ‘T’ and ‘G’) characters. Since the number of such subsequences may be very large, print the answer modulo $10^9 + 7$.

A sequence $b$ is a subsequence of a string $a$ if $b$ can be obtained from $a$ by deleting some (possibly zero or all) elements.

Input

The input starts with a line containing two space-separated integers $n$ and $q$, denoting the number of characters in $s$ and the number of queries $q$ respectively. The second line contains the string $s$, which consists of $n$ characters, each of which are either ‘A’, ‘C’, ‘T’ or ‘G’. Note that the first character of the string is considered to be $s[1]$ (1-based indexing).

$q$ lines follow, each of which contains two integers, specifying $l$ and $r$ as described above.

Constraints

$1 \leq n, q \leq 10^5$

$1 \leq l \leq r \leq n$

Output

Output $q$ lines, specifying the answer to each query in the order in which they appear in the input.

Sample

Input	Output
15 5 ACTTTGCCATATAAT 1 10 6 10 9 15 9 14 3 6	315 3 0 0 0