*Based on the Vietnamese folklore "Hundred-knot bamboo tree"*

Once upon a time, there was a wealthy landlord in a faraway village. He had a beautiful and kind daughter. From the same village, there was a hard-working lumberjack. Seeing his good inner quality, the landlord really wants to hire him. He promises: "Work hard for me for three years, and I shall allow you to marry my daughter.". Believing in these words, he worked day and night at his job, serving the landlord's will. Finally, after three years, the landlord is even richer, a lot of this thanks to the lumberjack's hard work. However, the landlord went down on his words; he didn't want to let his daughter go for the lumberjack. He makes an impossible request for the guy: bring him a thousand-knot bamboo tree and make a house with it; only then will he approve the marriage. A kind and honest person, the lumberjack quickly went to the forest to search for the bamboo tree. However, no matter how hard he tried, he couldn't find such a tree. He then sat down by a bamboo bush, crying with sadness. Suddenly, Buddha appeared and asked him what was going on. After hearing the lumberjack's story, he taught him the spell "Khắc nhập, khắc nhập" and suddenly every single bamboo trees that he has cut down joins into one.

The story happened in the land of VNOI, so every joint of a bamboo tree
has a lowercase Latin letter. Therefore, each bamboo tree can be
represented as a string of characters, with the first character
belonging to the base joint and the last character at the top joint. The
spell "Khắc nhập, khắc nhập" itself is also special: The bamboo trees
will be joined together to make a larger bamboo tree with the **smallest
possible lexicographical order**!

Illustration for the spell "Khắc nhập, khắc nhập" for the bamboo trees
represented by the string `tre`

, `is`

, `a`

, `long`

and `tree`

. The spell
connects all the trees into a single tree with the string `aislongtreetre`

which has the **smallest possible lexicographical order**.

But bringing home a thousand-knot bamboo tree is a task as impossible as
finding the tree itself. So Buddha teaches him another spell: "Khắc
xuất, khắc xuất". After reading the spell, the thousand-knot bamboo tree
gets split into several **shorter** trees, thereby allowing him to carry
them home easily, then use the spell "Khắc nhập, khắc nhập" to join the
trees back together.

Illustration for the spell "Khắc xuất, khắc xuất" for the bamboo tree
represented by the string `aislongtreetre`

into smaller bamboo trees with
strings `aisl`

, `ongtre`

and `etre`

. Note that this is not the only way
this tree can be cut into.

To outmaneuver the watchful eyes of the landlord, the lumberjack needs
to make sure that, when calling the two spells "Khắc xuất, khác xuất" to
split the tree, and then "Khắc nhập, khắc nhập" to join the trees, then
the string of the thousand-knot tree remains **unchanged** compared to
the original tree. If the two trees are different, the landlord can
quickly tell the fabrication of the new tree. Luckily, the lumberjack
easily manipulates the tree-splitting spell "Khắc xuất, khắc xuất" to
split the tree any way he desires.

Given a string ~S~ representing the thousand-knot bamboo tree (note that
the length of ~S~ is not necessarily ~1000~, *thousand* is just an
approximative namesake). Count the number of ways to use the splitting
spell "Khắc xuất, khắc xuất" to split the tree, such that when the
joining spell "Khắc nhập, khắc nhập" is called, all the tree parts will
join together to form a string exactly the same as the original string
~S~. There can possibly be many ways, so you should output the number of
ways modulo ~10^9 + 7~.

Two ways of using the splitting spell are different if the set of cut positions of the thousand-knot tree is different.

A string ~a~ is lexicographically smaller than a string ~b~ if and only if one of the following holds:

~a~ is a prefix of ~b~, but ~a \ne b~;

in the first position where ~a~ and ~b~ differ, the string ~a~ has a letter that appears earlier in the alphabet than the corresponding letter in ~b~.

#### Input

There are several test cases in one test file. The first line contains an integer ~t~ (~t \le 2000~), the number of tests. Each test are described as follow.

The first and only line of each test case contains a single string ~S~ (~1 \le |S| \le 2000~, ~S~ contains only lowercase Latin letters), representing the bamboo tree that the lumberjack has to carry home

The total length of all the strings within a single test file do not exceed ~2000~.

#### Output

For each test case, calculate the number of ways to use the spell "Khắc xuất, khắc xuất" to cut the tree, such that after using the spell "Khắc nhập, khắc nhập" to join the parts, the resulting tree is identical to the original string ~S~. Since the answer may be very large, output the answer modulo ~10^9 + 7~.

#### Scoring

Subtask 1 (~25~ points): The length of each bamboo tree does not exceed ~5~.

Subtask 2 (~100~ points): The total length of all the strings within a single test file do not exceed ~100~.

Subtask 3 (~234~ points): No additional constraints

The total score for this problem is ~359~.

#### Sample Input 1

```
3
a
acb
ababa
```

#### Sample Output 1

```
0
2
3
```

#### Notes

In the first test case, the bamboo is represented by the string `a`

. It
is impossible to split this tree.

In the second test case, the bamboo is represented by the string `acb`

.
There are two correct ways to split this tree:

Split into two trees represented by

`a`

and`cb`

,Split into two trees represented by

`ac`

and`b`

.

Note that splitting `acb`

into `a`

, `c`

and `b`

would be incorrect,
because after calling the joining spell "Khắc nhập, khắc nhập" on these
trees, the resulting tree would have the string `abc`

, which is
different from the original.

In the second test case, the bamboo is represented by the string
`ababab`

. The following three ways are the correct ways to split the
tree:

`a|baba`

,`aba|ba`

,`a|ba|ba`

.

Fun fact: The spells "Khắc nhập, khắc nhập" and "Khắc xuất, khắc xuất" can be literally translated to "Join together, join together" and "Split apart, split apart", respectively.

## Comments