#3115. 「SDOI2019」连续子序列

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Ycrpro

题目描述

我们定义 \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}