#P2022K. AvavaAva

    ID: 110 Type: Default 1000ms 256MiB Tried: 29 Accepted: 7 Difficulty: 7 Uploaded By: Tags>福建师范大学第19届程序设计竞赛

AvavaAva

AvavaAva

Time limit: 1 seconds

Memory limit: 512 megabytes

Problem Statement

Diana ask a simple question to Ava :

A string SS is given, each query will give an interval [l,r][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 109+710^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(1n,m500000)n,m(1 \leq n,m \leq 500000) denoting the length of string SS and the number of queries.

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

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

Output

Print mm lines, each line contains a integer, denoting the answer to each query modulo 109+710^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