Konkotenacja

Time limit2sMemory limit128 MB

Summary

Count the ways to split the word into nonempty pieces joined by the literal separator kot, modulo 1000000007.

Level: Medium5 of 10
Topics: Dynamic programming, Prefix sum, String matching
Solved: No attempts yet

Problem

The konkotenacja of two words A and B is the word AkotB, that is, the two words joined by the literal string kot. For example, the konkotenacja of mas and ka is maskotka.

The operation extends to a whole sequence of words: konkotenate all of them in order, inserting kot between every pair of consecutive words. For example, konkotenating the sequence (aa, b, cc, d) yields aakotbkotcckotd.

Given a word W, how many different sequences of non-empty words produce W when konkotenated?

Input

The first line contains one integer Z ( $1 \le Z \le 10$ ), the number of test cases.

Each of the next Z lines contains one non-empty word W made up of lowercase English letters only. The length of W does not exceed $1\,000\,000$ .

Output

For each word, print on its own line one non-negative integer: the number of different sequences that produce that word when konkotenated, taken modulo $1\,000\,000\,007$ .

Notes

The word maskotka can be produced by exactly two sequences: (mas, ka) and (maskotka).

The word akotkot can also be produced by exactly two sequences: (a, kot) and (akotkot).

Examples2

Example 1
Input
```
2
maskotka
akotkot
```
Expected output
```
2
2
```
Example 2
Input
```
1
aakotbkotcckotd
```
Expected output
```
8
```