405366: GYM101915 K Poor Ramzi

Ramzi is in a lot of troubles nowadays and he has a weird habit. When he starts thinking about his troubles, he takes a pen and starts writing a sequence of zeros and ones. We really don't know why!.

One day, he got sick of thinking about his problems and tried to keep himself busy by playing with the sequence he wrote. He divided the sequence into consecutive ranges, then he wrote down a new sequence consisting of the sum of digits in each range.

Once he finished, he noticed something, the sequence was palindromic. He called it a sumindrome sequence.

A palindromic sequence is a sequence that reads the same backward as forward, such as {3, 5, 7, 5, 3}. Ramzi wants to know how lucky he is, so he is interested in the number of different ways of dividing the original sequence leading to a sumindrome sequence. Ramzi doesn't like huge numbers, so he wants the answer modulo (10⁹ + 7).

Can you help him and give him the answer?

The first line contains a single integer T denoting the number of test cases.

Each test case consists of one line which contains the original sequence of zeros and ones.

The length of every sequence is less than or equal to 50.

For each test print one line containing one integer, the number of different ways to divide the original sequence leading to a sumindrome sequence modulo (10⁹ + 7).

2
0110
1001

4
8

The ways of dividing the sequence in the second sample are:

(1001) -> 2

(1)(001) -> 1, 1

(100)(1) -> 1, 1

(10)(01) -> 1, 1

(1)(00)(1) -> 1, 0, 1

(1)(0)(01) -> 1, 0, 1

(10)(0)(1) -> 1, 0, 1

(1)(0)(0)(1) -> 1, 0, 0, 1