Thousand-knot bamboo tree

View as PDF

Submit solution

Points: 1.60 (partial)
Time limit: 2.0s
Memory limit: 1G
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
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!

image

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.

image

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

Please read the guidelines before commenting.


There are no comments at the moment.