Cipher

题目翻译： 对于单词（字符串） $s$ ，保证它只由小写字母组成。 设 $ s$ 的长度为 $len$ ，下文单词（字符串）下标从 $1$ 开始. 如果一个词可以通过零次或多次运算转换成另一个词，则我们认为这两个词的意思是一致的。 运算仅仅包含以下两种方式。 - 方式一：指定任意一个位置 $p$ $(1 \le p \le len)$使 $s_p$ 上的字母变成 **字母表上** 的后一个字母(如 a 变成 b ，x 变成 y)，而 $s_{p+1}$ 则要变成 **字母表上** 的前一个字母(如 d 变成 c)。 - 方式二：指定任意一个位置 $p$ $(1 \le p \le len)$使 $s_p$ 上的字母变成 **字母表上** 的前一个字母，而 $s_{p+1}$ 则要变成 **字母表上** 的后一个字母。 你需要回答对于输入的单词，一共有多少种与它意思一致的单词。 另外，对于字母 a ，不能将它变成前一个字母（因为它在字母表上没有前一个字母），同理 字母 z 也不能变成后一个字母。 给出多个单词（字符串），你需要分别对它们做出回答。 输入格式： 第一行一个数字 $t$ 表示单词的个数。$(t \le 10^4)$ 接下来每行一个单词，长度不大于 $100$ 。 输出格式： 共 $t$ 行,每行一个数，表示对于每个单词的答案对 $1000000007$ 取模的结果。 By vijone

Sherlock Holmes found a mysterious correspondence of two VIPs and made up his mind to read it. But there is a problem! The correspondence turned out to be encrypted. The detective tried really hard to decipher the correspondence, but he couldn't understand anything. At last, after some thought, he thought of something. Let's say there is a word $ s $ , consisting of $ |s| $ lowercase Latin letters. Then for one operation you can choose a certain position $ p $ ( $ 1<=p&lt;|s| $ ) and perform one of the following actions: - either replace letter $ s_{p} $ with the one that alphabetically follows it and replace letter $ s_{p+1} $ with the one that alphabetically precedes it; - or replace letter $ s_{p} $ with the one that alphabetically precedes it and replace letter $ s_{p+1} $ with the one that alphabetically follows it. Let us note that letter "z" doesn't have a defined following letter and letter "a" doesn't have a defined preceding letter. That's why the corresponding changes are not acceptable. If the operation requires performing at least one unacceptable change, then such operation cannot be performed. Two words coincide in their meaning iff one of them can be transformed into the other one as a result of zero or more operations. Sherlock Holmes needs to learn to quickly determine the following for each word: how many words can exist that coincide in their meaning with the given word, but differs from the given word in at least one character? Count this number for him modulo $ 1000000007 $ $ (10^{9}+7) $ .

The input data contains several tests. The first line contains the only integer $ t $ ( $ 1<=t<=10^{4} $ ) — the number of tests. Next $ t $ lines contain the words, one per line. Each word consists of lowercase Latin letters and has length from $ 1 $ to $ 100 $ , inclusive. Lengths of words can differ.

For each word you should print the number of different other words that coincide with it in their meaning — not from the words listed in the input data, but from all possible words. As the sought number can be very large, print its value modulo $ 1000000007 $ $ (10^{9}+7) $ .

1
ab

1

1
aaaaaaaaaaa

0

2
ya
klmbfxzb

24
320092793

Some explanations about the operation: - Note that for each letter, we can clearly define the letter that follows it. Letter "b" alphabetically follows letter "a", letter "c" follows letter "b", ..., "z" follows letter "y". - Preceding letters are defined in the similar manner: letter "y" precedes letter "z", ..., "a" precedes letter "b". - Note that the operation never changes a word's length. In the first sample you can obtain the only other word "ba". In the second sample you cannot obtain any other word, so the correct answer is $ 0 $ . Consider the third sample. One operation can transform word "klmbfxzb" into word "klmcexzb": we should choose $ p=4 $ , and replace the fourth letter with the following one ("b" $ → $ "c"), and the fifth one — with the preceding one ("f" $ → $ "e"). Also, we can obtain many other words from this one. An operation can transform word "ya" only into one other word "xb". Word "ya" coincides in its meaning with words "xb", "wc", "vd", ..., "ay" (overall there are $ 24 $ other words). The word "klmbfxzb has many more variants — there are $ 3320092814 $ other words that coincide with in the meaning. So the answer for the first word equals $ 24 $ and for the second one equals $ 320092793 $ — the number $ 3320092814 $ modulo $ 10^{9}+7 $