# #P2022K. AvavaAva

# AvavaAva

# 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
```