Konkotenacją słów A i B nazwiemy słowo AkotB. Przykładowo konkotenacją słów "mas" oraz "ka" jest słowo "maskotka". Operację tę można zdefiniować dla całych ciągów słów - konkotenujemy wtedy ze sobą wszystkie słowa zgodnie z kolejnością, z jaką w danym ciągu występują. I tak po skonkotenowaniu ciągu słów ( "aa", "b", "cc", "d" ) otrzymujemy słowo "aakotbkotcckotd".</p>

Ile różnych ciągów złożonych z niepustych słów daje po skonkotenowaniu dane słowo W?

입력 형식

W pierwszej linii znajduje się jedna liczba naturalna Z ( 1 <= Z <= 10 ) oznaczająca liczbę zestawów testowych. W kolejnych liniach opisywane są kolejne zestawy.</p>

Pojedynczy zestaw składa się z jednego niepustego słowa W złożonego z małych liter alfabetu angielskiego. Długość słowa W nie przekracza 1 000 000.

출력 형식

Dla każdego słowa podanego na wejściu należy wypisać w osobnej linii jedną nieujemną liczbę całkowitą - resztę z dzielenia liczby różnych ciągów dających po skonkotenowaniu dane słowo przez 1 000 000 007.

예제 입력

2
maskotka
akotkot

예제 출력

2
2