Description

小 A 穿越到了古老的字母国，这个国家的语言仅由两个字母 ${a, b}$ 组成。小 A 对这样的语言很是头疼，所以他通过远程电话询问了某位不知名的语言大师。这位大师告诉小 A，这个语言有一个神奇的地方，就是有许多单词表示的是同一个意思。具体来说，假设小 A 现在得到了一个由字符集 ${a, b}$ 构成的单词 $s$，那么将 $s$ 进行下列操作得到的单词与 $s$ 具有相同的含义。

1. 将两个连续的 $b$ 替换为 $a$，例如 $bba$ 变为 $aa$；
2. 将两个连续的 $a$ 替换为 $b$，例如 $aab$ 变为 $bb$。

这样的操作可以进行无限次，得到的单词均与 $s$ 具有相同的含义。现在小 A 想知道，对于自己拿到的这个单词 $s$，经过若干次上述操作后（可以不进行操作），有多少个不同的单词与单词 $s$ 有相同的含义。小 A 通过远程电话找到了你，不过小 A 只需要你给出答案对于 $(10^9 + 7$) 取模后的结果即可。由于小 A 还可能遇到很多单词，所以你需要支持多组询问。

Format

Input

输入文件第一行，一个数 $T$，表示数据组数。 接下来 $T$ 行，一个字符串 $s$，表示小 A 拿到的单词。

Output

输出文件共 $T$ 行。 每行回答一个询问，一个数，表示经过若干次操作后（可以不进行操作）， 有多少个不同的单词与单词 $s$ 有相同的含义，答案对 $(10^9 + 7)$ 取模。

Samples

2
aaaa
aabb

6
5

见下发文件

见下发文件

Limitation

• 对于 30% 的数据，$|s| \leq 10$；
• 对于 50% 的数据，$|s| \leq 10^3$；
• 对于 100% 的数据，$|s| \leq 10^5$，$1 \leq T \leq 100$，保证 $s$中只包含 ${a, b}$。