← 返回题目列表

Codeforces · 156/C

C. 密码

中文机器翻译题面 查看原题

夏洛克·福尔摩斯发现了一封两位重要人物的神秘信件,并决定阅读它。但有一个问题!事实证明,这些信件是经过加密的。侦探非常努力地试图破译这些信件,但他什么也看不懂。

终于,他想了想,想到了一件事。假设有一个单词 s,由 |s| 组成。小写拉丁字母。然后,对于一个操作,您可以选择某个位置 p (1 ≤ p < |s|) 并执行以下操作之一:

- 将字母 sp 替换为按字母顺序排列在其后面的字母,并将字母 sp + 1 替换为按字母顺序排列在其前面的字母;
- 或将字母 sp 替换为按字母顺序排列在其前面的字母,并将字母 sp + 1 替换为按字母顺序排列在其后面的字母。

让我们注意,字母“z”没有定义的后一个字母,字母“a”没有定义的前一个字母。这就是为什么相应的改变是不可接受的。如果该操作需要执行至少一项不可接受的改变,则不能执行这样的操作。

两个词的含义一致,前提是其中一个词可以通过零次或多次操作转换为另一个词。

夏洛克·福尔摩斯需要学会快速确定每个单词的以下内容:可以存在多少个单词与给定单词的含义一致,但至少有一个字符与给定单词不同?以 1000000007 (109 + 7) 为模计算他的这个数字。

输入

输入数据包含多个测试。第一行包含唯一的整数 t (1 ≤ t ≤ 104) — 测试次数。

接下来 t 行包含单词,每行一个。每个单词均由小写拉丁字母组成,长度为 1 到 100(含 1 和 100)。单词的长度可能不同。

输出

对于每个单词,您应该打印与其含义一致的不同其他单词的数量 - 不是来自输入数据中列出的单词,而是来自所有可能的单词。由于要查找的数字可能非常大,因此打印其模 1000000007 (109 + 7) 的值。

示例

输入 #1

1
ab

输出 #1

1

输入 #2

1
aaaaaaaaaaa

输出 #2

0

输入 #3

2
ya
klmbfxzb

输出 #3

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