你知道这个问题吗（https://atcoder.jp/contests/agc022/tasks/agc022_e）？我们对其进行了一点推广。

你有一个长度为 8 的二进制字符串 $P = P_0P_1P_2P_3P_4P_5P_6P_7$。

你认为一个长度为奇数 $N$ 的二进制字符串 $X$ 是“美丽的”，如果可以通过执行以下操作 $\frac{N-1}{2}$ 次，使得最终剩下的唯一字符为 ‘1’：

• 选择 $X$ 中的三个连续位 $(X_i, X_{i+1}, X_{i+2})$，并将它们替换为 $P$ 的第 $(X_i + 2X_{i+1} + 4X_{i+2})$ 位。

注意，当 $P = 00010111$ 时，该定义与原 AGC 问题相同。

你有一个由字符 ‘0’、‘1’ 和 ‘?’ 组成的字符串 $S$。你想知道有多少种方法可以将问号替换为 ‘1’ 或 ‘0’，使得结果字符串是美丽的，结果对 $10^9 + 7$ 取模。

注意，一个输入文件中包含 $T$ 组测试数据。

输入格式

输入通过标准输入给出，格式如下：

$T$ $P$ $S$ $P$ $S$ $\vdots$ $P$ $S$

数据范围：

• $1 \le T \le 256$
• $|P| = 8$
• $1 \le |S|$ 且 $\sum |S| \le 300,000$
• $|S|$ 为奇数。
• $P$ 的所有字符均为 ‘0’ 或 ‘1’。
• $S$ 的所有字符均为 ‘0’、‘1’ 或 ‘?’。

输出格式

对于每组测试数据，输出一行答案。

样例

样例输入 1

7
00010111 1??00
00010111 ?
00010111 ?0101???10???00?1???????????????0????????????1????0
01010101 1????
01010101 0????
00001111 1????
00001111 0????

样例输出 1

2
1
402589311
16
0
8
8