[SDOI2019] 连续子序列
题目描述
我们定义 $\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
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}$