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 ss consisting of nn characters, each of which are either A, C, T or G, you are to output the results of qq queries.

Each query specifies two integers ll and rr. 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]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 109+710^9 + 7.

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

Input

The input starts with a line containing two space-separated integers nn and qq, denoting the number of characters in ss and the number of queries qq respectively. The second line contains the string ss, which consists of nn 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]s[1] (1-based indexing).

qq lines follow, each of which contains two integers, specifying ll and rr as described above.

Constraints

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

1lrn1 \leq l \leq r \leq n

Output

Output qq 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

    Discussion

    Statistics


    100% Solution Ratio

    amirhozaifaEarliest, 2w ago

    steinumFastest, 0.0s

    pathanLightest, 2.8 MB

    steinumShortest, 515B

    Submit

    Login to submit