Konkotenacja

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?

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$.

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$.

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).