균형 이진 문자열

Chiaki는 '0', '1', '?'로 이루어진 길이 $n$의 문자열 $s$를 가지고 있다.

$s=s_1s_2 \dots s_n$의 원형 부분 문자열 $s(i,l)$은 다음과 같은 문자열이다.

$\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}$

길이 $n$의 이진 문자열 $s$가 균형이라는 것은, 임의의 두 원형 부분 문자열 $s(i,l)$과 $s(j,l)$ ($1 \le i, j, l \le n$)에 대해 $s(i,l)$과 $s(j,l)$에 들어 있는 '1'의 개수가 많아야 1만큼 차이 나는 것을 말한다. 예를 들어 $101$과 $11010110$은 균형이지만, $1100$과 $1010110110$은 균형이 아니다.

Chiaki는 자신의 문자열에서 모든 '?'를 '0' 또는 '1'로 바꾸어 문자열을 균형으로 만드는 방법의 수를 알고 싶어 한다. 이 수는 매우 클 수 있으므로 $10^9+7$로 나눈 나머지를 계산하면 된다.

여러 개의 테스트 케이스가 주어진다. 입력의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 $T$가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에는 '0', '1', '?'로 이루어진 비어 있지 않은 문자열 $s$가 주어진다. ($1 \le |s| \le 1024$)

모든 테스트 케이스에서 $|s|$의 합은 $1024$를 넘지 않는다.

각 테스트 케이스마다 방법의 수를 나타내는 정수를 한 줄에 출력한다.