23488번 - Balanced Binary String 다국어

문제

Chiaki has a string $s$ of length $n,ドル consisting of '0', '1' and '?'.

A circular substring $s(i,l)$ of $s=s_1s_2 \dots s_{n}$ is string $\begin{cases} s_i s_{i+1} \dots s_{i + l - 1} & i + l - 1 \le n \\ s_is_{i+1} \dots s_n s_1 s_2 \dots s_{i + l - 1 - n} & i + l - 1 > n \end{cases}$.

A binary string $s$ of length $n$ is balanced if for every two circular substrings $s(i,l)$ and $s(j,l)$ (1ドル \le i, j, l \le n$), the number of 1ドル$'s in $s(i,l)$ and $s(j,l)$ differ at most by one. For example, 101ドル$ and 11010110ドル$ are balanced, while 1100ドル$ and 1010110110ドル$ are not balanced.

Chiaki would like to know the number of ways to replace every '?' to '0' or '1' in her string to make it balanced. Since this number may be very large, you are only asked to calculate it modulo 10ドル^9+7$.

입력

There are multiple test cases. The first line of input contains an integer $T,ドル indicating the number of test cases. For each test case:

The first line contains a nonempty string $s$ (1ドル \le |s| \le 1024$) consisting of '0', '1' and '?'.

It is guaranteed that the sum of $|s|$ over all test cases does not exceed 1024ドル$.

출력

For each test case, output an integer denoting the number of ways.

제한

힌트