CF156C Cipher

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

The input data contains several tests. The first line contains the only integer $ t $ ( $ 1

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) $ .

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 $