Chef is given a binary string S of length N.

In one operation, Chef has to choose exactly K indices and flip their values.

Chef can perform the above operation any number of times. Find the number of distinct binary strings Chef can obtain.

Since the answer might be large, output it module 10^{9} + 7.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains two space-separated integers N and K, as mentioned in statement.
- The next line contains the binary string S.

------ Output Format ------ 

For each test case, output the number of distinct binary strings Chef can obtain, modulo 10^{9} + 7.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ K ≤ N$
- Sum of $N$ over all test cases do not exceed $3 \cdot 10^{5}$.

----- Sample Input 1 ------ 
2
4 1
0010
2 2
00

----- Sample Output 1 ------ 
16
2

----- explanation 1 ------ 
Test case $1$: We can flip $1$ index in an operation. Thus, we can generate all possible binary strings of length $4$. The total number of distinct strings that can be generated are $2^{4} = 16$. 

Test case $2$: We have to flip $2$ indices at once. Thus, we can convert $00$ to $11$. The only possible strings that can be generated are $00$ and $11$. Thus, the answer is $2$.

Difficulty: VERY_HARD
Tags: Mathematics

Starter code:

Solutions:
import sys
import math
import collections
import random
from heapq import heappush, heappop
from functools import reduce
input = sys.stdin.readline
ints = lambda : list(map(int, input().split()))
MOD = 10 ** 9 + 7

def solve() -> None:
	(n, k) = map(int, input().split())
	s = str(input())
	if k == n:
		print(2)
	elif k & 1:
		print(pow(2, n, MOD))
	else:
		print(pow(2, n - 1, MOD))
t = int(input())
for _ in range(t):
	solve()


for i in range(int(input())):
	(n, k) = map(int, input().split())
	b = int(input())
	if n == k:
		print(2)
	elif k % 2 == 1:
		print(2 ** n % (10 ** 9 + 7))
	else:
		print(2 ** (n - 1) % (10 ** 9 + 7))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	if n == k:
		print(2)
	elif k % 2 == 1:
		print(2 ** n % 1000000007)
	else:
		print(2 ** (n - 1) % 1000000007)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	if n == k:
		print(2)
	elif k % 2 == 1:
		print(2 ** n % (10 ** 9 + 7))
	else:
		print(2 ** (n - 1) % (10 ** 9 + 7))


for i in range(int(input())):
	(N, K) = map(int, input().split())
	a = int(input())
	if N == K:
		print(2)
	elif K % 2 == 1:
		print(2 ** N % (10 ** 9 + 7))
	else:
		print(2 ** (N - 1) % (10 ** 9 + 7))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	if k == n:
		print(2)
	elif k % 2 == 0:
		print(pow(2, n - 1, 10 ** 9 + 7))
	else:
		print(pow(2, n, 10 ** 9 + 7))


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	s = input()
	if n == k:
		print(2)
	elif k == 1:
		print(2 ** n % 1000000007)
	elif k % 2 == 0:
		print(2 ** (n - 1) % 1000000007)
	else:
		print(2 ** n % 1000000007)
	t -= 1


import math
mod = 1000000007
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	if n == k:
		print('2')
	elif k % 2 == 0:
		print(pow(2, n - 1, mod))
	else:
		print(pow(2, n, mod))


T = int(input())
while T != 0:
	(N, K) = map(int, input().split())
	S = int(input())
	if K == N:
		print(2)
	elif K % 2 == 0:
		print(2 ** (N - 1) % (10 ** 9 + 7))
	else:
		print(2 ** N % (10 ** 9 + 7))
	T -= 1


def f(n, k, str):
	if k == n:
		return 2
	elif k % 2 == 0:
		return 2 ** (n - 1) % (10 ** 9 + 7)
	else:
		return 2 ** n % (10 ** 9 + 7)
t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	str = input()
	res = f(n, k, str)
	print(res)
	t -= 1


from math import comb
t = int(input())
m = 1000000007
for i in range(0, t):
	a = list(map(int, input().split()))
	s = input()
	if a[0] == a[1]:
		print(2)
	elif a[1] % 2 == 0:
		print(pow(2, a[0] - 1, m))
	else:
		print(pow(2, a[0], m))


m = 1000000007

def po(num, p):
	power = 1
	for i in range(0, p):
		power = power % m * num % m % m
	return power
t = int(input())
s = ''
while t > 0:
	a = [int(i) for i in input().strip().split()]
	n = a[0]
	k = a[1]
	s = input()
	if n == k:
		print('2')
	elif k % 2 != 0:
		print(po(2, n))
	else:
		print(po(2, n - 1))
	t -= 1


import math
t = int(input())
mod = 1000000007
for _ in range(t):
	(n, k) = map(int, input().split())
	str = input()
	if n == k:
		print(2)
	elif k % 2 == 1:
		print(pow(2, n, mod))
	else:
		print(pow(2, n - 1, mod))


mod = 10 ** 9 + 7
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	a = input()
	if N == K:
		print(2)
	elif K < N and K % 2 == 1:
		print(2 ** N % mod)
	else:
		print(2 ** (N - 1) % mod)


import sys
input = sys.stdin.readline
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = int(input())
	if n == q:
		print(2)
	else:
		print(2 ** n % mod if q % 2 != 0 else 2 ** (n - 1) % mod)


T = int(input())
for i in range(T):
	(x, p) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	if x == p:
		print(2)
	elif p < x and p % 2 == 0:
		print(2 ** (x - 1) % (10 ** 9 + 7))
	elif p < x and p % 2 != 0:
		print(2 ** x % (10 ** 9 + 7))


t = int(input())
for _ in range(t):
	(x, y) = list(map(int, input().split()))
	s = input()
	if x == y:
		print(2)
	elif y < x:
		if y % 2 != 0:
			print(2 ** x % 1000000007)
		else:
			print(2 ** (x - 1) % 1000000007)


from sys import stdin, stdout
from collections import deque
T = int(stdin.readline())
while T > 0:
	T -= 1
	(n, k) = map(int, stdin.readline().split())
	s = stdin.readline()
	if k == n:
		print('2')
		continue
	if k % 2 == 0:
		b = n - 1
	else:
		b = n
	modulo = 7 + pow(10, 9)
	bb = b % (modulo - 1)
	ans = pow(2, bb)
	ans = ans % modulo
	print(ans)


import math, copy
for i in range(int(input())):
	a = list(map(int, input().strip().split()))
	b = input()
	if a[0] == a[1]:
		print(2)
	elif a[1] % 2 == 0:
		print(pow(2, a[0] - 1, 10 ** 9 + 7))
	else:
		print(pow(2, a[0], 10 ** 9 + 7))


M = 1000000007
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	S = input()
	if N == K:
		print(2)
	else:
		f = 1
		L = N if K % 2 == 1 else N - 1
		for i in range(L):
			f = f * 2 % M
		print(f)


t = int(input())
while t > 0:
	(n, k) = list(map(int, input().split(' ')))
	binary = input()
	if n == k:
		print(2)
	elif k < n:
		if k % 2 != 0:
			print(2 ** n % 1000000007)
		else:
			print(2 ** (n - 1) % 1000000007)
	t -= 1


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	string = [char for char in input()]
	if k == n:
		print('2')
	elif k % 2 == 0:
		print(2 ** (n - 1) % (10 ** 9 + 7))
	else:
		print(2 ** n % (10 ** 9 + 7))


from collections import Counter
from math import ceil, floor, log, gcd
import bisect as bs
import sys
input = sys.stdin.readline
inp_lis = lambda : list(map(int, input().split()))
inp_multi = lambda : map(int, input().split())
inp_int = lambda : int(input().strip())
mod = int(1000000000.0) + 7
for _ in range(int(input().strip())):
	(n, k) = inp_multi()
	s = input().strip()
	if k == n:
		print(2)
	elif k % 2 == 0:
		print(2 ** (n - 1) % mod)
	else:
		print(2 ** n % mod)


m = pow(10, 9) + 7
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	ans = 0
	if n == k:
		ans = 2
	elif k % 2 == 1:
		ans = pow(2, n, m)
	else:
		ans = pow(2, n - 1, m)
	print(ans)


import sys
from itertools import islice
for t in islice(sys.stdin, 1, None, 2):
	(n, q) = map(int, t.split())
	r = 2 if q == n else 1 << n - 1 + q % 2
	print(r % (10 ** 9 + 7))


import sys
from itertools import islice
for i in islice(sys.stdin, 1, None, 2):
	(n, k) = map(int, i.split())
	r = 2 if k == n else 1 << n - 1 + k % 2
	print(r % (10 ** 9 + 7))


def soln(N, K):
	if K == N:
		pw = 1
	elif K % 2 == 1:
		pw = N
	else:
		pw = N - 1
	return pw
mod = int(10 ** 9 + 7)
for t in range(int(input())):
	(N, K) = map(int, input().split())
	S = input()
	print(pow(2, soln(N, K), mod))


import math
m = int(pow(10, 9) + 7)
t = int(input())
for x in range(t):
	(n, k) = map(int, input().split())
	l = [int(i) for i in input()]
	if n == k:
		ans = 2
	elif k % 2 == 0:
		ans = pow(2, n - 1) % m
	else:
		ans = pow(2, n) % m
	print(ans)


x = int(input())
for i in range(x):
	(n, k) = map(int, input().split())
	s = int(input())
	m = 1000000007
	if n == k:
		print(2)
		continue
	if k % 2 == 1:
		print(2 ** n % m)
		continue
	else:
		print(2 ** (n - 1) % m)


mod = int(10 ** 9 + 7)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	s = input()
	if b == a:
		print(2)
	elif b < a and b % 2 == 1:
		print(pow(2, a, mod))
	elif b < a and b % 2 == 0:
		print(pow(2, a - 1, mod))


mod = int(10 ** 9 + 7)
T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	S = input()
	if N == K:
		print(2)
	elif K % 2 == 1:
		print(pow(2, N, mod))
	else:
		print(pow(2, N - 1, mod))


import math
from bisect import bisect, bisect_left, bisect_right
import heapq
from math import gcd, floor, sqrt, log
from collections import defaultdict as ddc
from collections import Counter

def intin():
	return int(input())

def mapin():
	return map(int, input().split())

def strin():
	return input().split()
INF = 10 ** 20
mod = 1000000007

def LIS(arr, n):
	dp = [10 ** 9] * (n + 1)
	for ele in arr:
		dp[bisect_left(dp, ele)] = ele
	return bisect_left(dp, 10 ** 9)

def exponentiation(bas, exp, mod=1000000007):
	t = 1
	while exp > 0:
		if exp % 2 != 0:
			t = t * bas % mod
		bas = bas * bas % mod
		exp //= 2
	return t % mod

def MOD(p, q=1, mod=1000000007):
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p
yes = 'YES'
no = 'NO'
even = 'EVEN'
odd = 'ODD'

def process(arr, n, k):
	if n == k:
		return 2
	if k % 2:
		return exponentiation(2, n)
	else:
		return exponentiation(2, n - 1)

def main():
	for _ in range(int(input())):
		(n, k) = mapin()
		arr = list(mapin())
		print(process(arr, n, k))
main()


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = input()
	print(2 if k == n else pow(2, n - (1 - k % 2), 10 ** 9 + 7))


t = int(input())
if t >= 1 and t <= 10 ** 4:
	for i in range(t):
		(n, k) = map(int, input().split(' '))
		l = input()
		if n >= 1 and n <= 10 ** 5 and (k >= 1) and (k <= n):
			if n == k:
				print('2')
			elif k % 2 == 1:
				print(pow(2, n, 10 ** 9 + 7))
			else:
				print(pow(2, n - 1, 10 ** 9 + 7))


t = int(input())
dp = [0] * 100001
dp[0] = 1
mod = 1000000007
for i in range(1, 100001):
	dp[i] = dp[i - 1] * 2 % mod

def solve(N, K):
	if K == 1:
		return dp[N]
	if K == N:
		return 2
	if K % 2 == 1:
		return dp[N]
	return dp[N - 1]
for _ in range(t):
	(N, K) = tuple(map(int, input().split()))
	input()
	print(solve(N, K))


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	x = int(input())
	if k == n:
		ans = 2
	elif k % 2 == 0:
		ans = pow(2, n - 1, 10 ** 9 + 7)
	else:
		ans = pow(2, n, 10 ** 9 + 7)
	print(ans)


for i in range(int(input())):
	MOD = 10 ** 9 + 7
	(n, k) = map(int, input().split())
	s = input().replace(' ', '').strip()
	if n == k:
		print(2)
	elif k % 2 == 1:
		print(2 ** n % MOD)
	else:
		print(pow(2, n - 1) % MOD)


from itertools import combinations
mod = pow(10, 9) + 7
T = int(input())
for t in range(T):
	(n, k) = map(int, input().split())
	s = input()
	if k == n:
		print(2)
	elif k % 2 == 0:
		print(pow(2, n - 1) % mod)
	else:
		print(pow(2, n) % mod)


T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	s = input()
	if n == k:
		print(2)
	elif k == 1:
		print(2 ** n % 1000000007)
	elif k % 2 == 0:
		print(2 ** (n - 1) % 1000000007)
	else:
		print(2 ** n % 1000000007)