密令

题目描述

给定一小写字母串 $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$。