Description

Given a lowercase string $s$, in each operation you may choose a position $p$ ($1 \leq p \lt |s|$) and perform one of the following modifications:

1. Change $s_p$ to the letter with lexicographic order $+1$, and change $s_{p+1}$ to the letter with lexicographic order $-1$.
2. Change $s_p$ to the letter with lexicographic order $-1$, and change $s_{p+1}$ to the letter with lexicographic order $+1$.

After performing any number of operations, into how many different strings can $s$ be transformed?

During the modifications, $s$ must always remain a valid lowercase string (that is, you cannot apply lexicographic $-1$ to the letter 'a', and you cannot apply lexicographic $+1$ to the letter 'z'). Output the answer modulo $10^9 + 7$.

Input Format

The first line contains an integer $T$, the number of test cases.

The next $T$ lines each contain a lowercase string $s$.

Output Format

Output $T$ lines, each containing one integer, the answer for the corresponding test case.

3
aaaaaaaaa
ya
klmbfxzb

0
24
320092793

Hint

• For $30\%$ of the testdata, $T = 1$, $|s| \leq 10$.
• For $60\%$ of the testdata, $T \leq 10$.
• For $100\%$ of the testdata, $T \leq 10000$, $1 \leq |s| \leq 100$.

Translated by ChatGPT 5