P5362 [SDOI2019] Consecutive Subsequences

We define the $\textbf{T. M.}$ sequence $\{T_n\}$ as a Boolean sequence of the following form: - $T_0=0$. - $T_{2n}=T_n$. - $T_{2n+1}=1-T_n$. Here are the first several terms of the $\textbf{T. M.}$ sequence: $01101001100101101001011001101001\cdots$. The $\textbf{T. M.}$ sequence is an infinite sequence, and it has many consecutive subsequences. For example, $0$, $1$, $10100$, $10011$, and $011001$ are all consecutive subsequences of it, while $111$ and $1000$ are not. Now you are given a Boolean sequence (a 01 string) $S$ and a non-negative integer $k$. Please count how many different consecutive subsequences $T$ of the $\textbf{T. M.}$ sequence satisfy: - $S$ is a prefix of $T$. - $T$ is formed by appending exactly $k$ more terms to the right of $S$.

The first line contains an integer $T$, indicating that there are $T$ test cases. Then follow $T$ lines. Each line contains a 01 string $S$ (representing a Boolean sequence) and a non-negative integer $k$, describing one test case.

For each test case, output one line containing an integer, indicating the number of consecutive subsequences that satisfy the conditions. Since the value may be very large, output it modulo $10^9+9$.

Subtask $1$ ($20$ points): $1\le T\le 100$, the length of the given Boolean sequence is at most $100$, and $0\le k\le 100$. Subtask $2$ ($20$ points): $1\le T\le 100$, the length of the given Boolean sequence is at most $100$, and $0\le k\le 50000$. Subtask $3$ ($60$ points): $1\le T\le 100$, the length of the given Boolean sequence is at most $100$, and $0\le k\le 10^{18}$. Translated by ChatGPT 5