[SDOI2019]连续子序列

题号：NC50819
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

我们定义 $\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，为给定的一组数据。

输出描述:

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

示例1

输入

复制

输出

复制

备注:

子任务1（20分）：，给定布尔序列长度不超过100，且。
子任务2（20分）：，给定布尔序列长度不超过100，且。
子任务3（60分）：，给定布尔序列长度不超过100，且。