密令
题目描述
给定一小写字母串 $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$ 行,每行一个整数表示答案。
输入输出样例
输入样例 #1
3
aaaaaaaaa
ya
klmbfxzb
输出样例 #1
0
24
320092793
说明
- 对于 $30\%$ 的数据,$T=1$,$|s| \leq 10$;
- 对于 $60\%$ 的数据,$T \leq 10$;
- 对于 $100\%$ 的数据,$T \leq 10000$,$1 \leq |s| \leq 100$。