AvavaAva

Time limit: 1 seconds

Memory limit: 512 megabytes

Problem Statement

Diana ask a simple question to Ava :

A string $S$ is given, each query will give an interval $[l,r]$, you need to answer how many subsequences of string "AVA" are in this interval.

Since the answer may be very large, you only need to print the result modulo $10^9 + 7$.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e, "ace" is a subsequence of "abcde" while "aec" is not).

Input

The first line contains two integers $n,m(1 \leq n,m \leq 500000)$ denoting the length of string $S$ and the number of queries.

The second line contains a string $S$. It is guaranteed that each character in $S$ is 'A' or 'v'.

In the following $m$ lines, each line contains two integers $l,r(1 \leq l \leq r \leq n)$ denoting a query.

Output

Print $m$ lines, each line contains a integer, denoting the answer to each query modulo $10^9 + 7$.

8 5
AvAvAAvA
1 3
1 5
2 4
1 8
5 8

1
4
0
14
2

5 2
AvvvA
1 5
1 4

3
0