题目描述

我们定义 $\textbf{T. M.}$ 序列 $\{T_n\}$ 为如下形式的布尔序列：

• $T_0=0$；
• $T_{2n}=T_n$；
• $T_{2n+1}=1-T_n$。

这里我们给出 $\textbf{T. M.}$ 序列的前若干项：$01101001100101101001011001101001\cdots$ 。

$\textbf{T. M.}$ 序列是一个无限长度的序列，它有很多连续子序列。
例如 $0$ ，$1$ ，$10100$ ，$10011$ 和 $011001$ 都是它的连续子序列，然而 $111$ 和 $1000$ 却不是它的连续子序列。

现在给定一个布尔序列（ $01$ 字符串）$S$ 和一个非负整数 $k$ ，请统计一下一共有多少种 $\textbf{T. M.}$ 序列的连续子序列 $T$ 满足：

• $S$ 是 $T$ 的前缀；
• $T$ 是由 $S$ 额外在右侧添加了恰好 $k$ 项形成的。

输入格式

第一行给定一个整数 $T$，表示输入一共含有 $T$ 组数据。

之后 $T$ 行，每一行给定一个 $01$ 字符串 $S$（表示一个布尔序列）和一个非负正整数 $k$，为给定的一组数据。

输出格式

对于每一组数据，输出一行并含有一个整数，表示满足条件的连续子序列个数。因为数值可能很大，请输出关于 $10^9+9$ 取模后的值。

样例

5
1001 3
11001 10
00111 10
0011 20
0 100

3
4
0
6
164

数据范围与提示

子任务 $1$（$20$ 分）：$1\le T\le 100$，给定布尔序列长度不超过 $100$，且 $0\le k\le 100$。

子任务 $2$（$20$ 分）：$1\le T\le 100$，给定布尔序列长度不超过 $100$，且 $0\le k\le 50000$。

子任务 $3$（$60$ 分）：$1\le T\le 100$，给定布尔序列长度不超过 $100$，且 $0\le k\le 10^{18}$。