快攻猛男的早餐
题号：NC231894
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

早晨，有 n 道菜顺序摆在 BreakFast 的面前。由于 BreakFast 比较挑食，因此他对每道菜会表现出喜欢或者不喜欢。同时，BreakFast 还具有强迫症，他必须把一段连续的菜作为早餐。但为了不影响 BreakFast 的好心情，他至多只会吃 k 道不喜欢的菜。

现在你想知道 BreakFast 的早餐一共有几种方案。

两种方案不同当且仅当两种方案中存在至少一道菜不一样。

输入描述:

第一行输入一个整数  表示有 T 组测试数据。

对于每组测试数据，先输入两个整数 ，接下来一行输入一个长度为 n 的字符串 s。若  为 0 则表示 BreakFast 不喜欢第 i 道菜，否则若  为 1 则表示 BreakFast 喜欢第 i 道菜。

保证 。

输出描述:

对于每组测试数据，输出一个整数表示 BreakFast 早餐的方案数。
示例1

输入

复制 
2
8 4
01001000
3 3
111

输出

复制 
32
6

备注:

BreakFast's breakfast