F. Kilani The Tiger (Hard)
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of the problem; the difference between the easy and hard versions is that the hard version requires queries.

Kilani the tiger is the greatest competitive programmer not only in ASZoo but also in the world. And he's well known as Az3ar, but at home they call him "keko", and he doesn't like this name.

He found a string with $$$n$$$ characters, and he wants to find the number of subsequences in the string that contain the word "keko" to determine whether people already know his name.

Given a string $$$s$$$ that consists of $$$n$$$ lowercase Latin letters. And you'll be given $$$q$$$ queries, on each query, find how many subsequences are equal to the word "keko" in the substring in range $$$l$$$, $$$r$$$ ($$$1 \le l \le r \le |s|$$$).

More formally, find the number of subsequences that equals "keko" in the substring $$$s_l, s_{l+1}, s_{l+2}, ..., s_{r-1}, s_3$$$.

The answer will be very large. So, print it modulo $$$1\,000\,000\,007$$$.

A subsequence of a string is a string that can be obtained by removing several (possibly zero) characters from the original string.

For example, consider the string "abac", "aa", "ac", "ba" are subsequences of it, but "ca" is not.

Input

The input contains only one test case.

The first line consists of a single integer $$$n$$$, $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$).

The second line consists of a string $$$s$$$ ($$$|s| = n$$$)

The next $$$q$$$ lines consists of two integer $$$l_i$$$, $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$).

Output

For each query, print the answer modulo $$$1\,000\,000\,007$$$..

Example
Input
6 4
kkkeko
1 6
2 6
3 6
1 5
Output
3
2
1
0