## NOIP '20 P2 - String Matching

View as PDF

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

Little C has just finished learning about string matching, and he is practicing now.

For a string , the question asks him to find the number of ways to split in the following form:

, , , where , , are all non-empty strings. The number of characters appearing an odd number of times in will not be more than the number of characters appearing an odd number of times in .

More specifically, we can define to represent the concatenation of two strings and . For example , , then .

We also recursively define , ( and is a positive integer). For example, , then .

Little C's problem is asking to find the number of ways of , where ; represents the number of characters that appear an odd number of times in . Two ways are considered different if and only if at least one string in the split , and is different.

Little C doesn't know how to solve this problem, so he asked you for help.

#### Input Specification

A positive integer in the first line of the input file represents the number of data sets in the input.

The next lines contain a string for each data set on each line. consisting of lowercase letters only.

#### Output Specification

For each data set, output a line with one integer indicating the answer.

#### Sample Input 1

3
nnrnnr
zzzaab
mmlmmlo

#### Sample Output 1

8
9
16

#### Explanation for Sample 1

All possible ways are

1. , , .
2. , , .
3. , , .
4. , , .
5. , , .
6. , , .
7. , , .
8. , , .

#### Sample Input 2

5
kkkkkkkkkkkkkkkkkkkk
lllllllllllllrrlllrr
cccccccccccccxcxxxcc
ccccccccccccccaababa
ggggggggggggggbaabab

#### Sample Output 2

156
138
138
147
194

Additional samples can be found here.

• Sample 3 (string3.in and string3.ans).
• Sample 4 (string4.in and string4.ans).

#### Constraints

None
None
None
contains only one character
contains only two characters
None
None

For all test cases, , .

Problem translated to English by Tommy_Shan.