Chiaki 有一个长度为 $n$ 的字符串 $s$，由字符 '0'、'1' 和 '?' 组成。

对于 $s = s_1s_2 \dots s_n$，其循环子串 $s(i, l)$ 定义为： $$ s(i, l) = \begin{cases} s_i s_{i+1} \dots s_{i+l-1} & i + l - 1 \le n \\ s_i s_{i+1} \dots s_n s_1 s_2 \dots s_{i+l-1-n} & i + l - 1 > n \end{cases} $$

如果一个长度为 $n$ 的二进制字符串 $s$ 满足：对于任意两个长度为 $l$ 的循环子串 $s(i, l)$ 和 $s(j, l)$ ($1 \le i, j, l \le n$)，它们中 '1' 的个数之差不超过 1，则称该字符串是平衡的。例如，101 和 11010110 是平衡的，而 1100 和 1010110110 不是平衡的。

Chiaki 想知道有多少种方法可以将字符串中的每个 '?' 替换为 '0' 或 '1'，使得最终的字符串是平衡的。由于结果可能非常大，你只需要输出其对 $10^9 + 7$ 取模的结果。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个非空字符串 $s$ ($1 \le |s| \le 1024$)，由 '0'、'1' 和 '?' 组成。

保证所有测试数据的 $|s|$ 之和不超过 1024。

输出格式

对于每组测试数据，输出一个整数，表示方案数。

样例

输入格式 1

10
?
??
??1
???0
????1
?????0
??????1
???????0
????????1
?????????0

输出格式 1

2
4
4
6
11
11
22
22
31
32