J. Median Replace Hard
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Do you know this problem(https://atcoder.jp/contests/agc022/tasks/agc022_e)? We generalize it a bit.

You got a binary string $$$P = P_0P_1P_2P_3P_4P_5P_6P_7$$$ of length $$$8$$$.

You think a binary string $$$X$$$ of odd length $$$N$$$ is beautiful if it is possible to apply the following operation $$$\frac{N-1}{2}$$$ times so that the only character of the resulting string is '1' :

  • Choose three consecutive bits of $$$X$$$, $$$(X_i,X_{i + 1},X_{i + 2})$$$, and replace them by the $$$(X_i + 2X_{i + 1} + 4X_{i + 2})$$$-th bit of $$$P$$$.

Note that, when $$$P = 00010111$$$, this definition is the same as the original AGC problem.

You have a string $$$S$$$ consisting of characters '0', '1', and '?'. You want to know the number of ways to replace the question marks with '1' or '0' so that the resulting string is beautiful, modulo $$$10^9 + 7$$$.

Note that there are $$$T$$$ tests in one input file.

Input

Input is given from Standard Input in the following format:

$$$T$$$

$$$P$$$ $$$S$$$

$$$P$$$ $$$S$$$

$$$\vdots$$$

$$$P$$$ $$$S$$$

Constraints:

  • $$$1 \leq T \leq 256$$$
  • $$$|P|=8$$$
  • $$$1 \leq |S|$$$ and $$$\sum {|S|} \leq 300,000$$$
  • $$$|S|$$$ is odd.
  • All characters of $$$P$$$ are either '0' or '1'.
  • All characters of $$$S$$$ are either '0', '1', or '?'.
Output

For each case, print the answer in a line.

Example
Input
7
00010111 1??00
00010111 ?
00010111 ?0101???10???00?1???????????????0????????????1????0
01010101 1????
01010101 0????
00001111 1????
00001111 0????
Output
2
1
402589311
16
0
8
8