Konkotenacja

두 단어 A, B의 콘코테나차(konkotenacja) 는 두 단어를 문자열 kot으로 이어 붙인 단어 AkotB로 정의한다. 예를 들어 mas와 ka의 콘코테나차는 maskotka이다.

이 연산은 단어들의 수열 전체로 확장된다. 수열에 있는 모든 단어를 등장 순서대로 이어 붙이되, 인접한 두 단어 사이마다 kot을 끼워 넣는다. 예를 들어 수열 (aa, b, cc, d)를 콘코테나차하면 aakotbkotcckotd가 된다.

단어 W가 주어질 때, 비어 있지 않은 단어들로 이루어진 서로 다른 수열 중에서 콘코테나차했을 때 W가 되는 것은 몇 개인가?

첫째 줄에 정수 Z ($1 \le Z \le 10$), 즉 테스트 케이스의 개수가 주어진다.

이어지는 Z개의 줄에는 각각 소문자 영어 알파벳으로만 이루어진 비어 있지 않은 단어 W가 하나씩 주어진다. W의 길이는 $1\,000\,000$을 넘지 않는다.

각 단어에 대해, 콘코테나차했을 때 그 단어가 되는 서로 다른 수열의 개수를 $1\,000\,000\,007$로 나눈 나머지를 한 줄에 하나씩 음이 아닌 정수로 출력한다.

단어 maskotka는 정확히 두 개의 수열 (mas, ka)와 (maskotka)로부터 얻을 수 있다.

단어 akotkot 역시 정확히 두 개의 수열 (a, kot)와 (akotkot)로부터 얻을 수 있다.