连续子序列

连续子序列

测试数据来自 system/2056

描述

我们定义 \(\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\)取模后的值。

样例1

样例输入1

5
1001 3
11001 10
00111 10
0011 20
0 100

样例输出1

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}\)。

时限

1s

内存限制

默认

信息

ID
1105
难度
(无)
分类
(无)
标签
(无)
递交数
0
已通过
0
通过率
?
上传者