Bob has received a binary string of length N transmitted by Alice. He knows that due to errors in transmission, up to K bits might have been corrupted (and hence flipped). However, he also knows that the string Alice had intended to transmit was not periodic. A string is not periodic if it cannot be represented as a smaller string concatenated some number of times. For example, "0001", "0110" are not periodic while "00000", "010101" are periodic strings.

Now he wonders how many possible strings could Alice have transmitted.

Input Format

The first line contains the number of test cases T. T test cases follow. Each case contains two integers N and K on the first line, and a binary string of length N on the next line.

Constraints

$1\leq T\leq20$ 

$1\leq N\leq1000$ 

$0\leq K\leq N$  

Output Format

Output T lines, one for each test case. Since the answers can be really big, output the numbers modulo 1000000007.

Sample Input 0
3  
5 0  
00000  
3 1  
001  
3 3  
101

Sample Output 0
0
3
6

Explanation 0

Explanation: For the second example, Alice could have transmitted "001", or "011" or "101". 

For the third example, Alice could have transmitted 001, 010, 100, 011, 101, 110

Difficulty: MEDIUM_HARD
Tags: Bit manipulation
Skill types: Bit manipulation

Starter code:

Solutions:
T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


import sys
sol_mod = 1000000007
div_cache = dict()

def divisors(n):
	if n in div_cache:
		return div_cache[n]
	ret = []
	for i in range(1, n // 2 + 1):
		if n % i == 0:
			ret.append(i)
	div_cache[n] = ret
	return ret

def gen_subwords(word, size):
	ret = []
	index = 0
	while index < len(word):
		ret.append(word[index:index + size])
		index += size
	return ret

def gen_bin_costs(subwords):
	ret = []
	for i in range(len(subwords[0])):
		(pos, neg) = (0, 0)
		for subword in subwords:
			if subword[i]:
				pos += 1
			else:
				neg += 1
		ret.append((pos, neg))
	return ret

def num_ways(bin_costs, cost_limit):
	prev_ways = [1] + [0] * cost_limit
	for cand_costs in bin_costs:
		num_ways = [0] * len(prev_ways)
		for cost in range(len(prev_ways)):
			if prev_ways[cost] > 0:
				for cand in cand_costs:
					if cost + cand <= cost_limit:
						num_ways[cost + cand] = (num_ways[cost + cand] + prev_ways[cost]) % sol_mod
		prev_ways = num_ways
	return sum(prev_ways) % sol_mod

def fac_mod(n, mod, stop=1):
	tot = 1
	while n > stop:
		tot = tot * n % mod
		n -= 1
	return tot

def choose_mod_prime(x, y, mod):
	num = fac_mod(x, mod, stop=y)
	dom = fac_mod(x - y, mod)
	return num * pow(dom, mod - 2, mod) % mod

def total_ways(word_size, cost_limit):
	tot = 0
	for cost in range(cost_limit + 1):
		tot += choose_mod_prime(word_size, cost, sol_mod)
	return tot % sol_mod

def count_periodics(lookup, divs):
	num_periodics = 0
	visited = set()
	ex_lookup = dict()
	for div in divs:
		ex = lookup[div]
		for subdiv in divisors(div):
			ex -= ex_lookup[subdiv]
		ex_lookup[div] = ex
	return sum(ex_lookup.values())

def sol(word, cost_limit):
	divs = divisors(len(word))
	lookup = dict()
	for div in divs:
		subwords = gen_subwords(word, div)
		costs = gen_bin_costs(subwords)
		res = num_ways(costs, cost_limit)
		lookup[div] = res
	num_periodics = count_periodics(lookup, divs)
	total_words = total_ways(len(word), cost_limit)
	return (total_words - num_periodics) % sol_mod

def reachable_words(word, cost_limit, part=None, index=None):
	if part is None:
		part = [False] * len(word)
	if index is None:
		index = 0
	if index == len(part):
		yield part
	else:
		part[index] = word[index]
		for cand in reachable_words(word, cost_limit, part, index + 1):
			yield cand
		if cost_limit > 0:
			part[index] = not word[index]
			for cand in reachable_words(word, cost_limit - 1, part, index + 1):
				yield cand

def is_periodic(word, divs):
	for div in divs:
		subwords = gen_subwords(word, div)
		costs = gen_bin_costs(subwords)
		all_zero = True
		for bin_cost in costs:
			if 0 not in bin_cost:
				all_zero = False
		if all_zero:
			return True
	return False

def naive(word, cost_limit):
	divs = divisors(len(word))
	ret = 0
	for cand_word in reachable_words(word, cost_limit):
		if not is_periodic(cand_word, divs):
			ret += 1
	return ret

def solve(in_file, out_file):
	num_cases = int(in_file.readline().strip())
	for _ in range(num_cases):
		(_, limit) = [int(val) for val in in_file.readline().strip().split(' ')]
		word = [int(val) == 1 for val in in_file.readline().strip()]
		out_file.write('{}\n'.format(sol(word, limit)))
import random

def gen_rand():
	word_size = random.randrange(12, 30)
	cost_limit = random.randrange(0, 4)
	word = [random.random() < 0.5 for _ in range(word_size)]
	return (word, cost_limit)

def find_counter():
	accept = True
	while accept:
		(word, cost) = gen_rand()
		accept = sol(word, cost) == naive(word, cost)
	print(word)
	print(cost)
from_file = False
if from_file:
	path = 'Data\\'
	name = 'binstring'
	file_input = open(path + name + '.in', 'r')
	file_output = open(path + name + '.out', 'w')
	solve(file_input, file_output)
	file_input.close()
	file_output.close()
else:
	solve(sys.stdin, sys.stdout)


import os
import sys
from math import factorial, sqrt
import math
T = int(input())
MOD = 1000000007

def binomialCoeff(n, k):
	ans = 0
	for i in range(k + 1):
		ans += factorial(n) // (factorial(i) * factorial(n - i))
	return ans

def findDivisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = binomialCoeff(N, K)
	div = findDivisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	periodicFlag = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			periodicFlag = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - periodicFlag) % MOD)


import os
import sys
from math import factorial, sqrt
import math
MOD = 1000000007

def binomialCoeff(n, k):
	ans = 0
	for i in range(0, k + 1):
		ans = ans + factorial(n) // (factorial(i) * factorial(n - i))
	return ans

def findDivisors(n):
	divSet1 = [1]
	divSet2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			divSet1.append(i)
			if i * i != n:
				divSet2.append(n // i)
	divSet1.extend(divSet2[::-1])
	return divSet1

def main():
	try:
		test_cases = int(input())
	except:
		print('Test cases must be an int')
		return
	for test_case_number in range(test_cases):
		try:
			nk = input()
			n = int(nk.split(' ')[0])
			k = int(nk.split(' ')[1])
		except:
			print('Something went wrong with the formatting, please check the instructions')
			return
		try:
			s_trans = input()
		except:
			print('something went wrong with the input')
		if n == 1:
			print(1 + k)
			continue
		total = binomialCoeff(n, k)
		div = findDivisors(n)
		nkSum = n + k + 1
		result = [[0] * nkSum for i in range(len(div))]
		isPeriodic = 0
		i = 0
		for d in div:
			result[i][0] = 1
			for offset in range(d):
				zeros = 0
				for j in range(offset, n, d):
					if s_trans[j] == '0':
						zeros = zeros + 1
				ones = n // d - zeros
				prev = list(result[i])
				result[i][:] = [0] * nkSum
				for k in range(k + 1):
					if prev[k]:
						kZ = k + zeros
						kO = k + ones
						result[i][kZ] = result[i][kZ] + prev[k]
						result[i][kO] = result[i][kO] + prev[k]
			if result[i][0]:
				isPeriodic = 1
			for z in range(i):
				divTemp = div[z]
				if d % divTemp == 0:
					for k in range(k + 1):
						result[i][k] = result[i][k] - result[z][k]
			for k in range(1, k + 1):
				total = total - result[i][k]
			i += 1
		print((total - isPeriodic) % MOD)
main()


import os
import sys
from math import factorial, sqrt
import math
MOD = 1000000007

def pascalRule(n, k):
	ans = -1
	for i in range(0, k + 1):
		ans = ans + factorial(n) // (factorial(i) * factorial(n - i))
	return ans

def countZeroes(myStr, counter, strlen, divisor):
	zeros = 0
	for j in range(counter, strlen, divisor):
		if myStr[j] == '0':
			zeros += 1
	return zeros

def findDivisors(n):
	divSet1 = [1]
	divSet2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			divSet1.append(i)
			if i * i != n:
				divSet2.append(n // i)
	divSet1.extend(divSet2[::-1])
	return divSet1

def main():
	try:
		test_cases = int(input())
	except:
		print('Test cases must be an int')
		return
	for test_case_number in range(test_cases):
		try:
			nk = input()
			n = int(nk.split(' ')[0])
			k = int(nk.split(' ')[1])
		except:
			print('Something went wrong with the formatting, please check the instructions')
			return
		try:
			s_trans = input()
		except:
			print('something went wrong with the input')
		if n == 1:
			print(1 + k)
			continue
		total = pascalRule(n, k) + 1
		div = findDivisors(n)
		nkSum = n + k + 1
		result = [[0] * nkSum for i in range(len(div))]
		isPeriodic = 0
		for (i, d) in enumerate(div):
			result[i][0] = 1
			for offset in range(d):
				zeros = countZeroes(s_trans, offset, n, d)
				ones = n // d - zeros
				prev = list(result[i])
				result[i][:] = [0] * nkSum
				for x in range(k + 1):
					if prev[x]:
						k0 = x + zeros
						k1 = x + ones
						result[i][k0] = result[i][k0] + prev[x]
						result[i][k1] = result[i][k1] + prev[x]
			isPeriodic = 1 if result[i][0] else isPeriodic
			for z in range(i):
				divTemp = div[z]
				if d % divTemp == 0:
					for k in range(k + 1):
						result[i][k] = result[i][k] - result[z][k]
			for k in range(1, k + 1):
				total = total - result[i][k]
		print((total - isPeriodic) % MOD)
main()


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
T = int(input())
M = 1000000007
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


import math
import os
import random
import re
import sys
T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


import math
import os
import random
import re
import sys
T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


import math
import os
import random
import re
import sys
T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


rr = int(input())
gg = 1000000007
from math import factorial, sqrt

def nck(QR, KIK):
	sol = 0
	for xx in range(KIK + 1):
		sol += factorial(QR) // (factorial(xx) * factorial(QR - xx))
	return sol

def divisors(QR):
	jijju = [1]
	kikku = []
	for xx in range(2, int(sqrt(QR)) + 1):
		if QR % xx == 0:
			jijju.append(xx)
			if xx * xx != QR:
				kikku.append(QR // xx)
	jijju.extend(kikku[::-1])
	return jijju
for _ in range(rr):
	(lali, kuli) = [int(x) for x in input().split()]
	balma = input()
	if lali == 1:
		print(lali + kuli)
		continue
	pura = nck(lali, kuli)
	viba = divisors(lali)
	valmki = [[0] * (lali + kuli + 1) for xx in range(len(viba))]
	is_periodic = False
	for (xx, d) in enumerate(viba):
		valmki[xx][0] = 1
		for offset in range(d):
			zeros = 0
			for zx in range(offset, lali, d):
				if balma[zx] == '0':
					zeros += 1
			numsi = lali // d - zeros
			puran = list(valmki[xx])
			valmki[xx][:] = [0] * (lali + kuli + 1)
			for KIK in range(kuli + 1):
				if puran[KIK]:
					valmki[xx][KIK + zeros] += puran[KIK]
					valmki[xx][KIK + numsi] += puran[KIK]
		if valmki[xx][0]:
			is_periodic = True
		for i2 in range(xx):
			kikku = viba[i2]
			if d % kikku == 0:
				for KIK in range(kuli + 1):
					valmki[xx][KIK] -= valmki[i2][KIK]
		for KIK in range(1, kuli + 1):
			pura -= valmki[xx][KIK]
	print((pura - is_periodic) % gg)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


import math
import os
import random
import re
import sys
T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


import math
import os
import random
import re
import sys
T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


G = int(input())
C = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(G):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % C)


G = int(input())
C = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(G):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % C)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)


T = int(input())
M = 1000000007
from math import factorial, sqrt

def nck(n, k):
	res = 0
	for i in range(k + 1):
		res += factorial(n) // (factorial(i) * factorial(n - i))
	return res

def divisors(n):
	d1 = [1]
	d2 = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d1.append(i)
			if i * i != n:
				d2.append(n // i)
	d1.extend(d2[::-1])
	return d1
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	S = input()
	if N == 1:
		print(N + K)
		continue
	total = nck(N, K)
	div = divisors(N)
	dp = [[0] * (N + K + 1) for i in range(len(div))]
	is_periodic = False
	for (i, d) in enumerate(div):
		dp[i][0] = 1
		for offset in range(d):
			zeros = 0
			for j in range(offset, N, d):
				if S[j] == '0':
					zeros += 1
			ones = N // d - zeros
			prev = list(dp[i])
			dp[i][:] = [0] * (N + K + 1)
			for k in range(K + 1):
				if prev[k]:
					dp[i][k + zeros] += prev[k]
					dp[i][k + ones] += prev[k]
		if dp[i][0]:
			is_periodic = True
		for i2 in range(i):
			d2 = div[i2]
			if d % d2 == 0:
				for k in range(K + 1):
					dp[i][k] -= dp[i2][k]
		for k in range(1, K + 1):
			total -= dp[i][k]
	print((total - is_periodic) % M)