407333: GYM102766 G Singhal and Broken Keyboard (hard version)

If you want to practice topicwise questions in the ladder way like a2oj , do register on my site http://codedigger.tech after the contest. Here you will get Handpicked Topicwise Questions from codeforces, codechef, uva and spoj for your better practice. Best of Luck.

The only difference between easy and hard versions is that you have to tell the number of distinct strings in easy version but you have to tell the number of distinct palindromic string in hard version.

Singhal brings a new keyboard consisting of only two English lowercase letters a and b. Somehow keyboard is broken and whenever he press a letter to print on screen , it prints the letter twice or thrice.

Example — If he press letter a , then aa or aaa gets printed on the screen with equal probability.

He wonders that how many distinct palindromic string will be printed on the screen if he press letters of a string $$$S$$$ in sequence.

Example — If $$$S = $$$ aba , then he first press a, then b and at last a.

As the answer can be rather large, print the remainder after dividing it by $$$1000000007 (10^9 + 7)$$$.

Note : A palindromic string is a string that reads the same backward as forward, for example strings z, aaa, aba, abccba are palindromes, but strings codedigger, codealittle, ab are not.

The first line contains a single integer $$$t (1 \le t \le 10^5)$$$ — the number of test cases in the input. Then $$$t$$$ test cases follow.

Each query contains a single string $$$S (1\le |S| \le 10^5)$$$ consisting of only two letters a and b. $$$|S|$$$ is the length of the string.

It is guaranteed that the total sum of $$$|S|$$$ is at most $$$10^5$$$.

For each test from the input print the number of distinct palindrome string modulo $$$1000000007 (10^9 + 7)$$$. Print the answers to the tests in the order in which the tests are given in the input.

4
a
ab
aba
aa

2
0
4
3

In the first query — The strings which can be print on screen if he press a are aa or aaa From these strings all are palindrome also, so number is 2.

In the second query — The strings which can print on screen are aabb or aaabb or aabbb or aaabbb. None of them are palindrome.

In the last query — The strings which can print on screen are aaaa or aaaaa or aaaaa or aaaaaa . Note that all strings are palindrome and two strings are same , we have to find the distinct palindrome strings.