题目描述

Sherlock Holmes 找到了两位大人物之间的神秘通信，打算读一读。但有麻烦：这些通信是加密的。侦探绞尽脑汁也没看懂一个字。

终于，他想出了一点门道。设有一个由 $|s|$ 个小写拉丁字母组成的单词 $s$。一次操作是指选定某个位置 $p$（$1 \le p \lt |s|$），然后执行以下两种动作之一：

• 把字母 $s_p$ 换成字母表中紧随其后的字母，同时把字母 $s_{p+1}$ 换成字母表中紧邻其前的字母；
• 或把字母 $s_p$ 换成字母表中紧邻其前的字母，同时把字母 $s_{p+1}$ 换成紧随其后的字母。

注意：字母 "z" 没有后继字母，字母 "a" 没有前驱字母，因此相应的替换是不允许的。若一次操作涉及至少一个不允许的替换，则该操作不能执行。

两个单词意义相同，当且仅当其中一个可以经过零次或多次操作变成另一个。

Sherlock Holmes 需要学会对每个单词快速回答：存在多少个单词，与给定单词意义相同、但至少有一个字符与它不同？请帮他数一数，答案对 $10^9+7$ 取模。

输入格式

输入包含多组测试。第一行是唯一的整数 $t$（$1 \le t \le 10^4$），表示测试组数。

接下来 $t$ 行，每行一个单词。每个单词由小写拉丁字母组成，长度在 1 到 100 之间（含）。单词的长度可以不同。

输出格式

对每个单词，输出与其意义相同的其他不同单词的个数——注意不是数输入中列出的单词，而是数所有可能的单词。由于所求个数可能很大，输出对 $10^9+7$ 取模后的值。

1
ab

1

1
aaaaaaaaaaa

0

2
ya
klmbfxzb

24
320092793

说明/提示

关于操作的一些说明：每个字母的后继字母是明确定义的——"b" 紧随 "a"，"c" 紧随 "b"，……，"z" 紧随 "y"。前驱字母同理："y" 前于 "z"，……，"a" 前于 "b"。注意操作永远不会改变单词的长度。

第一组样例中只能得到唯一的其他单词 "ba"。第二组样例无法得到任何其他单词，所以答案是 0。