406870: GYM102586 J Median Replace Hard

Memory Limit:1024 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

J. Median Replace Hardtime limit per test3 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard 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.

ExampleInput
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

加入题单

上一题 下一题 算法标签: