8797번 - Konkotenacja 다국어

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

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.

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.

Słowo "maskotka" można otrzymać z dwóch ciągów słów: ( "mas", "ka" ) oraz ( "maskotka" ).

Słowo "akotkot" również można otrzymać z dokładnie dwóch ciągów słów: ( "a", "kot" ) oraz ( "akotkot" ).