# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# DNA Demolition

By RHaque · Limits 1s, 512 MB

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

InputOutput
15 5
ACTTTGCCATATAAT
1 10
6 10
9 15
9 14
3 6

315
3
0
0
0


### Statistics

100% Solution Ratio

amirhozaifaEarliest, 2w ago

steinumFastest, 0.0s

pathanLightest, 2.8 MB

steinumShortest, 515B