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 consisting of characters, each of which are either A, C, T or G, you are to output the results of queries.
Each query specifies two integers and . You have to find the number of subsequences of the string formed by combining the characters 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 .
A sequence is a subsequence of a string if can be obtained from by deleting some (possibly zero or all) elements.
The input starts with a line containing two space-separated integers and , denoting the number of characters in and the number of queries respectively. The second line contains the string , which consists of characters, each of which are either ‘A’, ‘C’, ‘T’ or ‘G’. Note that the first character of the string is considered to be (1-based indexing).
lines follow, each of which contains two integers, specifying and as described above.
Output lines, specifying the answer to each query in the order in which they appear in the input.
15 5 ACTTTGCCATATAAT 1 10 6 10 9 15 9 14 3 6
315 3 0 0 0