C. Шифр
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Шерлок Холмс обнаружил тайную переписку двух неких очень важных личностей и твердо вознамерился ее прочитать. Но не тут-то было! Оказалось, что переписка зашифрована. Он долго бился над этим шифром, но ничего не мог понять.

Наконец, после некоторых раздумий, он осознал следующий факт. Пусть имеется слово s, состоящее из |s| строчных букв латинского алфавита. Тогда одной операцией можно выбрать некоторую позицию p (1 ≤ p < |s|) и сделать одно из двух:

  • либо букву sp заменить на следующую за ней в алфавитном порядке, и букву sp + 1 заменить на предшествующую ей в алфавитном порядке;
  • либо букву sp заменить на предшествующую ей в алфавитном порядке, и букву sp + 1 заменить на следующую за ней в алфавитном порядке.

Заметим, что для буквы «z» не определена следующая буква, а для буквы «a» не определена предыдущая буква. Поэтому соответствующие замены не допустимы. Если операция требует выполнения хотя бы одной недопустимой замены, то такую операцию нельзя выполнить.

Два слова совпадают по смыслу тогда и только тогда, когда одно можно получить из другого посредством выполнения нуля или более операций.

Шерлоку Холмсу требуется научиться быстро определять, сколько всего может существовать слов, совпадающих по смыслу с данным словом, но отличающихся от него хотя бы одним символом. Посчитайте для него это количество по модулю 1000000007 (109 + 7).

Входные данные

Во входных данных содержится несколько тестов. В первой строке записано единственное целое число t (1 ≤ t ≤ 104) — количество тестов.

В следующих t строках расположены сами слова, по одному слову в строке. Каждое слово состоит из строчных букв латинского алфавита и имеет длину от 1 до 100 включительно. Длины слов могут быть разными.

Выходные данные

Для каждого слова надо вывести количество различных других слов, которые совпадают с ним по смыслу — не среди слов, указанных во входных данных, а среди всех возможных слов. Поскольку искомое количество может быть очень большим, выведите его значение по модулю 1000000007 (109 + 7).

Примеры
Входные данные
1
ab
Выходные данные
1
Входные данные
1
aaaaaaaaaaa
Выходные данные
0
Входные данные
2
ya
klmbfxzb
Выходные данные
24
320092793
Примечание

Некоторые пояснения касательно операции:

  • Обратите внимание, что для каждой буквы следующая за ней определена однозначно. Буква «b» является следующей в алфавитном порядке за буквой «a», буква «c» является следующей за «b», ..., «z» является следующей за буквой «y».
  • Аналогичным образом определены и предшествующие буквы: буква «y» является предшествующей букве «z», ..., «a» является предшествующей букве «b».
  • Заметьте, что операция никогда не меняет длину слова.

В первом примере можно получить единственную другую строку — «ba».

Во втором примере нельзя получить такими действиями ни одной другой подстроки, поэтому правильный ответ — 0.

Рассмотрим подробнее третий пример. Из слова «klmbfxzb» за одну операцию можно получить слово «klmcexzb»: нужно выбрать p = 4, и заменить четвертую букву на следующую («b»  →  «c»), а пятую — на предшествующую («f»  →  «e»). Также из этого слова можно получить много других слов за одну операцию. Из слова «ya» за одну операцию можно получить только одно другое слово — «xb».

Слово «ya» совпадает по смыслу со словами «xb», «wc», «vd», ..., «ay» (всего 24 других слова). Для слова «klmbfxzb» вариантов гораздо больше — существует 3320092814 других слов, совпадающих с ним по смыслу. Ответ для первого слова 24, для второго 320092793 — это 3320092814 по модулю 109 + 7