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 (109 + 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 (109 + 7).
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
## Input
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.
## Output
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 (109 + 7).
[samples]
## Note
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
**Definitions**
Let $ s \in \{0,1\}^n $ be a binary sequence of length $ n \leq 50 $.
A *division* of $ s $ is a partition into $ k \geq 1 $ contiguous non-empty substrings $ s_1, s_2, \dots, s_k $, such that $ s = s_1 s_2 \cdots s_k $.
Let $ c_i = \sum_{x \in s_i} x $ be the sum of digits in substring $ s_i $.
The sequence $ C = (c_1, c_2, \dots, c_k) $ is called a *sum-sequence*.
**Constraints**
- $ 1 \leq T \leq \text{number of test cases} $
- For each test case, $ 1 \leq n \leq 50 $
**Objective**
For each binary sequence $ s $, count the number of divisions such that the resulting sum-sequence $ C $ is palindromic, i.e., $ c_i = c_{k+1-i} $ for all $ i \in \{1, \dots, k\} $.
Output the count modulo $ 10^9 + 7 $.