Description

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$.

Input Format

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.

Output Format

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$.

5
1001 3
11001 10
00111 10
0011 20
0 100

3
4
0
6
164

Hint

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