题目描述

给定一小写字母串 $s$，每次操作你可以选择一个 $p$（$1 \leq p \lt |s|$）执行下述修改中的任意一个：

1. 将 $s_p$ 改为其字典序 $+1$ 的字母，将 $s_{p+1}$ 改为其字典序 $-1$ 的字母；
2. 将 $s_p$ 改为其字典序 $-1$ 的字母，将 $s_{p+1}$ 改为其字典序 $+1$ 的字母。

在经过任意多次操作后，串 $s$ 能变化成多少种字符串？

修改过程中必须保证 $s$ 是合法的小写字母串（即不能对字母 a 进行字典序 $-1$ 的操作），答案对 $10^9 + 7$ 取模。

输入格式

第一行一个整数 $T$，表示数据组数

接下来 $T$ 行，每行一个小写字母串 $s$。

输出格式

输出 $T$ 行，每行一个整数表示答案。

3
aaaaaaaaa
ya
klmbfxzb

0
24
320092793

提示

• 对于 $30\%$ 的数据，$T=1$，$|s| \leq 10$；
• 对于 $60\%$ 的数据，$T \leq 10$；
• 对于 $100\%$ 的数据，$T \leq 10000$，$1 \leq |s| \leq 100$。