E. Kilani The Tiger (Easy)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the easy 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, find how many subsequences are equal to the word "keko"; 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 first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

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

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

The sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output

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

Example
Input
2
6
kkkeko
6
kkekoo
Output
3
4