NC50819. 连续子序列
描述
我们定义
序列
为如下形式的布尔序列：
序列是一个无限长度的序列，它有很多连续子序列。
例如0，1，10100，10011和011001都是它的连续子序列，然而111和1000却不是它的连续子序列。
现在给定一个布尔序列（01字符串）S和一个非负整数k，请统计一下一共有多少种序列的连续子序列T满足：
-
；
-
；
-
。
这里我们给出序列的前若干项：
。
例如0，1，10100，10011和011001都是它的连续子序列，然而111和1000却不是它的连续子序列。
现在给定一个布尔序列（01字符串）S和一个非负整数k，请统计一下一共有多少种
- S是T的前缀；
- T是由S额外在右侧添加了恰好k项形成的。
输入描述
第一行给定一个整数T，表示输入一共含有T组数据。
之后T行，每一行给定一个01字符串S（表示一个布尔序列）和一个非负正整数k，为给定的一组数据。
输出描述
对于每一组数据，输出一行并含有一个整数，表示满足条件的连续子序列个数。因为数值可能很大，请输出关于取模后的值。
示例1
输入:
5 1001 3 11001 10 00111 10 0011 20 0 100
输出:
3 4 0 6 164