23485번 - Median Replace Hard 다국어

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 is given from Standard Input in the following format:

$T$

$P$ $S$

$P$ $S$

$\vdots$

$P$ $S$

For each case, print the answer in a line.

• $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 '?'.