String Transmission

#!/usr/bin/env python


import sys


MOD = 1000000007


def divisors(n):
    d = 1
    while d * d <= n:
        if n % d == 0:
            yield d
            if d * d != n:
                yield n / d
        d += 1


def solve(N, K, S):
    factors = list(divisors(N))
    factors.sort()

    cost = [[[0, 0] for __ in range(N + 1)] for __ in range(N + 1)]
    for d in factors:
        for r in range(d):
            for k in range(N / d):
                if S[d * k + r] == '1':
                    cost[d][r][0] += 1
                if S[d * k + r] == '0':
                    cost[d][r][1] += 1

    dp = [0 for __ in range(N + 1)]
    for d in factors:
        subdp = [[0 for __ in range(K + 1)] for __ in range(d + 1)]
        for k in range(K + 1):
            subdp[0][k] = 1
        for r in range(d):
            for k in range(K + 1):
                if cost[d][r][0] <= k:
                    subdp[r + 1][k] += subdp[r][k - cost[d][r][0]]
                if cost[d][r][1] <= k:
                    subdp[r + 1][k] += subdp[r][k - cost[d][r][1]]
                subdp[r + 1][k] %= MOD

        dp[d] = subdp[d][K]
        for dd in divisors(d):
            if dd == d:
                continue  # only want proper divisors
            dp[d] -= dp[dd]
            dp[d] %= MOD

    return dp[N]


def main():
    T = int(next(sys.stdin))
    for t in range(T):
        N, K = map(int, next(sys.stdin).split())
        S = next(sys.stdin)
        print solve(N, K, S)


if __name__ == "__main__":
    main()