Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Chef has an array A consisting of N integers. He also has an intger K.

Chef wants you to find out number of different arrays he can obtain from array A by applying the following operation exactly K times.

Pick some element in the array and multiply it by -1

As answer could be quite large, print it modulo 10^{9} + 7.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space separated integers N, K as defined above.
The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N} denoting the elements of the array.

------ Output ------ 

For each test case, output a single line containing an integer corresponding to the number of different arrays Chef can get modulo 10^{9} + 7.

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

$1 ≤ T ≤ 10$
$1 ≤ N, K ≤ 10^{5}$
$-10^{6} ≤ A_{i} ≤ 10^{6}$

------ Subtasks ------ 

$Subtask #1 (10 points) : N, K ≤ 10$
$Subtask #2 (30 points) : N, K ≤ 100$
$Subtask #3 (60 points) : N, K ≤ 10^{5}$

----- Sample Input 1 ------ 
3

1 3

100

3 1

1 2 1

3 2

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

3

4
----- explanation 1 ------ 
Example case 1.
Chef has only one element and must apply the operation 3 times to it. After applying the operations, he will end up with -100. That is the only array he will get.

Example case 2.
Chef can apply operation to one of three elements. So, he can obtain three different arrays.

Example case 3.
Note that other than applying operation to positions (1, 2), (1, 3), (2, 3), Chef can also apply the operation twice on some element and get the original.

In summary, Chef can get following four arrays.

[1, 2, 1]
[-1, -2, 1]
[-1, 2, -1]
[1, -2, -1]

Difficulty: MEDIUM_HARD
Tags: Combinatorics

Mathematics

Starter code:

Solutions:
(MOD, p) = (10 ** 9 + 7, 10 ** 6 + 5)
fact = [0] * p
fact[0] = 1
for i in range(1, p):
	fact[i] = fact[i - 1] * i % MOD

def MI(a, MOD):
	return pow(a, MOD - 2, MOD)

def nck(n, k):
	if n == k or k == 0:
		return 1
	if n < k:
		return 0
	return fact[n] * MI(fact[k], MOD) % MOD * MI(fact[n - k], MOD) % MOD % MOD
MOD = 10 ** 9 + 7
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	(l, f) = ([int(i) for i in input().split()], 0)
	if 0 in l:
		f = 1
	(n, ans) = (n - l.count(0), 0)
	for x in range(0, min(n + 1, k + 1)):
		if (k - x) % 2 == 0 or f:
			ans = (ans + nck(n, x)) % MOD
	print(ans)


def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	return (x % m + m) % m
l = []
for i in range(100001):
	t = modinv(i + 1, 1000000007)
	l.append(t)
t = int(input())
m = 1
while m <= t:
	(n, k) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	flag = 0
	zero = 0
	for (i, val) in enumerate(a):
		if val == 0:
			flag = 1
			zero += 1
		else:
			continue
	if flag == 1:
		if zero == len(a):
			print(1)
		else:
			n -= zero
			if k >= n:
				p = 1
				for i in range(n):
					p = p % 1000000007 * (2 % 1000000007) % 1000000007
				print(p)
			else:
				c = 1
				val = 1
				for i in range(k):
					c = c % 1000000007 * ((n - (i + 1) + 1) % 1000000007) % 1000000007
					c = c * l[i] % 1000000007
					val += c
					val %= 1000000007
				print(val % 1000000007)
	elif k >= n - 1:
		p = 1
		for i in range(n - 1):
			p = p % 1000000007 * (2 % 1000000007) % 1000000007
		print(p)
	else:
		c = 1
		val = 1
		n -= 1
		for i in range(k):
			c = c % 1000000007 * ((n - (i + 1) + 1) % 1000000007) % 1000000007
			c = c * l[i] % 1000000007
			val += c
			val %= 1000000007
		print(val % 1000000007)
	m += 1


const = 1000000007
king_dict = {}
T = int(input())
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	mas = [int(x) for x in input().split()]
	zero_count = 0
	for x in mas:
		zero_count += x == 0
	N -= zero_count
	is_zero = zero_count != 0
	if N in king_dict:
		dct = king_dict[N]
	else:
		dct = {}
	if is_zero and K >= N:
		print(pow(2, N, const))
	else:
		if K % 2 == 0:
			ans = soch = 1
			i = 0
		else:
			ans = soch = N
			i = 1
			ans += is_zero
		dct[i] = soch
		dct[N - i] = soch
		while i < K and i < N:
			if i + 1 not in dct:
				soch *= N - i
				soch %= const
				soch *= pow(i + 1, const - 2, const)
				soch %= const
				dct[i + 1] = soch
				dct[N - i - 1] = soch
			else:
				soch = dct[i + 1]
			if is_zero:
				ans += soch
				ans %= const
			if i + 2 not in dct:
				soch *= N - i - 1
				soch %= const
				soch *= pow(i + 2, const - 2, const)
				soch %= const
				dct[i + 2] = soch
				dct[N - i - 2] = soch
			else:
				soch = dct[i + 2]
			ans += soch
			ans %= const
			i += 2
		print(ans)
		king_dict[N] = dct


t = int(input())
precalcodd = True
precalceven = True
presumodd = 0
presumeven = 0
preprododd = 1
preprodeven = 1

def comb(n, kk):
	global precalcodd, precalceven, presumodd, presumeven, preprododd, preprodeven
	sum = 0
	k = 1
	prod = 1
	flag = n % 2 == 0
	flag2 = kk % 2 == 0
	flag3 = n // 2 % 2 == 0
	nby2 = n // 2
	if kk >= 80000 and n == 100000:
		if precalcodd == True and kk % 2 != 0:
			precalcodd = False
			sum = 2 ** (n - 1)
			prod = n
			n -= 1
			k += 1
			sum -= prod
			while k < 15000:
				prod = prod * n * (n - 1) // (k * (k + 1))
				sum -= prod
				n -= 2
				k += 2
			presumodd = sum % (10 ** 9 + 7)
			preprododd = prod
		if precalceven == True and kk % 2 == 0:
			precalceven = False
			sum = 2 ** (n - 1)
			sum -= prod
			while k < 15000:
				prod = prod * n * (n - 1) // (k * (k + 1))
				sum -= prod
				n -= 2
				k += 2
			presumeven = sum % (10 ** 9 + 7)
			preprodeven = prod
		if kk % 2 != 0:
			sum = presumodd
			k = 15000
			n = 85001
			prod = preprododd
		else:
			sum = presumeven
			k = 15001
			n = 85000
			prod = preprodeven
		kkk = 100000 - kk - 2
		while k <= kkk:
			prod = prod * n * (n - 1) // (k * (k + 1))
			sum -= prod
			n -= 2
			k += 2
	elif kk > n // 2 and flag == True:
		if flag2 == False:
			prod = n
			n -= 1
			k += 1
		sum += prod
		while k + kk < nby2 * 2 - 1:
			prod = prod * n * (n - 1) // (k * (k + 1))
			sum += prod
			n -= 2
			k += 2
		while k + 2 < nby2:
			prod = prod * n * (n - 1) // (k * (k + 1))
			sum += prod * 2
			n -= 2
			k += 2
		prod = prod * n * (n - 1) // (k * (k + 1))
		if flag2 ^ flag3:
			sum += prod * 2
		else:
			sum += prod
	else:
		if kk % 2 != 0:
			prod = n // k
			n -= 1
			k += 1
		sum += prod
		while k <= kk:
			prod = prod * n * (n - 1) // (k * (k + 1))
			sum += prod
			n -= 2
			k += 2
	return sum

def comb2(n, kk):
	sum = 1
	k = 1
	prod = 1
	while k <= kk:
		prod = prod * n // k
		sum += prod
		n -= 1
		k += 1
	return sum
while t > 0:
	a = input().split(' ')
	b = list(map(int, input().split(' ')))
	n = int(a[0])
	k = int(a[1])
	if 0 in b:
		b = list(filter(0 .__ne__, b))
		n = len(b)
		if k >= n:
			print(2 ** n % (10 ** 9 + 7))
		else:
			print(int(comb2(n, k)) % (10 ** 9 + 7))
	elif k > n - 2:
		print(2 ** (n - 1) % (10 ** 9 + 7))
	else:
		print(int(comb(n, k)) % (10 ** 9 + 7))
	t -= 1


M = 1000000007
s = []
s += [1, 1]
f = 1
for i in range(2, 100001):
	f = f * i % M
	s += [f]

def computeit(n, k):
	c = [1 for i in range(k + 1)]
	res = 0
	if k <= int((n - 1) / 2) or k < 50000:
		res = c[0]
		for i in range(k):
			c[i + 1] = int(s[n - 1] * pow(s[n - i - 2] * s[i + 1] % M, M - 2, M)) % M
			res = (res + c[i + 1]) % M
	else:
		k = n - k - 2
		res = (pow(2, n - 1, M) - c[0]) % M
		for i in range(k):
			c[i + 1] = int(s[n - 1] * pow(s[n - i - 2] * s[i + 1] % M, M - 2, M)) % M
			res = (res - c[i + 1]) % M
	return res % M
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	o = x.count(0)
	if o == 0:
		if k >= n:
			u = pow(2, n - 1, M)
			print(u)
		else:
			print(computeit(n, k))
	else:
		n = n - o
		if k >= n:
			u = pow(2, n, M)
			print(u)
		else:
			print(computeit(n + 1, k))


def sumallbinomialCoeffuptok(n, k):
	s = 0
	while k >= 0:
		s += int(fact[n] * pow(fact[k] * fact[n - k] % Mod, Mod - 2, Mod))
		if s >= Mod:
			s %= Mod
		k -= 1
	return s

def sumselectedbinomialCoeffuptok(n, k):
	rem = k % 2
	s = 0
	while k >= 0:
		if k % 2 == rem:
			s += int(fact[n] * pow(fact[k] * fact[n - k] % Mod, Mod - 2, Mod))
			if s >= Mod:
				s %= Mod
		k -= 2
	return s
Mod = 10 ** 9 + 7
fact = [1]
for i in range(1, 10 ** 5 + 1):
	fact.append(fact[-1] * i % Mod)
T = int(input())
while T > 0:
	T -= 1
	(N, K) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	dec = 2
	if 0 in A:
		dec = 1
		N -= A.count(0)
	del A[:]
	if K >= N:
		print(pow(2, N - (dec - 1)) % Mod)
	elif dec == 1:
		print(sumallbinomialCoeffuptok(N, K))
	else:
		print(sumselectedbinomialCoeffuptok(N, K))


from math import *
prime = 10 ** 9 + 7

def gen():
	a = [1, 1]
	for i in range(2, 10 ** 5 + 5):
		a.append(a[i - 1] * i % prime)
	return a
f = gen()

def gen1():
	a = [1, 1]
	for i in range(2, 10 ** 5 + 5):
		a.append(a[i - 1] * mul_inv(i, prime) % prime)
	return a

def mul_inv(a, b):
	b0 = b
	x0 = 0
	x1 = 1
	if b == 1:
		return 1
	while a > 1:
		q = int(a / b)
		t = b
		b = a % b
		a = t
		t = x0
		x0 = x1 - q * x0
		x1 = t
	if x1 < 0:
		x1 += b0
	return x1
ifact = gen1()

def c(n, k):
	return f[n] * ifact[k] * ifact[n - k] % prime
t = int(input())
for i in range(t):
	count = 0
	s = input().split()
	n = int(s[0])
	k = int(s[1])
	a = [int(j) for j in input().strip().split()]
	flag = False
	for j in a:
		if j == 0:
			flag = True
		else:
			count += 1
	if k > count and flag == False:
		if (k - count) % 2 == 0:
			k = count
		else:
			k = count - 1
	if flag == True:
		k = min(count, k)
	ans = 0
	while k >= 0:
		ans += c(count, k)
		if flag == True:
			k -= 1
		else:
			k -= 2
	ans = ans % (10 ** 9 + 7)
	print(ans)


def inv(a):
	n = 1000000007
	(t, newt) = (0, 1)
	(r, newr) = (n, a)
	while newr != 0:
		q = r // newr
		(t, newt) = (newt, t - q * newt)
		(r, newr) = (newr, r - q * newr)
	if t < 0:
		t += n
	return t

def PowMod(n):
	(ret, a) = (1, 2)
	while n > 0:
		if n & 1:
			ret = ret * a % 1000000007
		a = a * a % 1000000007
		n >>= 1
	return ret

def binSum(n, k, z):
	n1 = n - z
	if k >= n1:
		return PowMod(n1)
	(n1Ci, ans) = (1, 1)
	for i in range(1, k + 1):
		n1Ci = n1Ci * (n1 - i + 1) * inv(i) % 1000000007
		ans = ans + n1Ci
	return ans % 1000000007

def binSum2(n, k):
	if k >= n:
		return PowMod(n - 1)
	if k & 1 == 0:
		(ans, nCi, start) = (1, 1, 2)
	else:
		(ans, nCi, start) = (n, n, 3)
	for i in range(start, k + 1, 2):
		nCi *= (n - (i - 1) + 1) * inv(i - 1)
		nCi %= 1000000007
		nCi *= (n - i + 1) * inv(i)
		nCi %= 1000000007
		ans += nCi
	return ans % 1000000007
t = int(input())
for _t in range(t):
	(N, K) = map(int, input().split())
	A = input()
	z = A.count(' 0') + (1 if A[0] == '0' else 0)
	if z > 0:
		print(binSum(N, K, z))
	else:
		print(binSum2(N, K))


NL = 100100
MOD = 1000000007
fact = [0] * NL
invfact = [0] * NL

def pre():
	fact[0] = invfact[0] = 1
	for i in range(1, NL):
		fact[i] = fact[i - 1] * i % MOD
		invfact[i] = pow(fact[i], MOD - 2, MOD)

def solve():
	inp = input().split()
	N = int(inp[0])
	K = int(inp[1])
	zc = 0
	inp = input().split()
	A = [0] * NL
	for i in range(0, N):
		A[i] = int(inp[i])
		if A[i] == 0:
			zc += 1
	if N - zc <= K:
		if zc == 0:
			print(pow(2, N - 1, MOD))
		else:
			print(pow(2, N - zc, MOD))
	elif zc == 0:
		ans = 0
		for k in range(K, -1, -2):
			ans += invfact[N - k] * invfact[k] % MOD
		ans = ans * fact[N] % MOD
		print(ans)
	else:
		ans = 0
		for k in range(K, -1, -1):
			ans += invfact[N - zc - k] * invfact[k] % MOD
		ans = ans * fact[N - zc] % MOD
		print(ans)
pre()
T = int(input())
for t in range(0, T):
	solve()


f = []
mod = 1000000007
for i in range(1, 100001):
	f.append(pow(i, mod - 2, mod))

def containsZero(n, k):
	if k is 1:
		print(n + 1)
	elif n - k is 1:
		ans = pow(2, n, mod)
		print((ans - 1).__mod__(mod))
	elif n - k <= 0:
		ans = pow(2, n, mod)
		print(ans.__mod__(mod))
	elif n - k >= 2:
		ans = 0
		current = 1
		for i in range(1, k + 1):
			current = current * (n - i + 1) * f[i - 1] % mod
			ans = (ans + current).__mod__(mod)
		print((ans + 1).__mod__(mod))

def poweroftwo(n):
	ans = pow(2, n, mod)
	return ans
t = int(input())
for q in range(t):
	s = input().strip().split(' ')
	(n, k) = (int(s[0]), int(s[1]))
	(num, numb) = (n, n)
	str = input().strip().split(' ')
	for x in range(n):
		if int(str[x]) is 0:
			numb -= 1
	if numb is not n:
		if numb is 0:
			print('1')
			continue
		elif numb is 1:
			print('2')
			continue
		else:
			containsZero(numb, k)
			continue
	if num is 1:
		print('1')
		continue
	elif k is 1:
		print(num)
		continue
	elif num - k <= 1:
		ans = poweroftwo(num - 1)
		print(ans % mod)
	elif num - k is 2:
		ans = poweroftwo(num - 1) - 1
		print(ans)
	else:
		ans = 0
		curr = 1
		if k % 2 is not 0:
			for i in range(1, k + 1, 2):
				if i is 1:
					curr = num
				else:
					curr = curr * (num - i + 1) * (num - i + 2) * f[i - 2] * f[i - 1] % mod
				ans = (ans + curr) % mod
			print(ans)
		else:
			ans = 0
			curr = 1
			for i in range(0, k + 1, 2):
				if i is 0:
					curr = 1
				else:
					curr = curr * (num - i + 1) * (num - i + 2) * f[i - 2] * f[i - 1] % mod
				ans = (ans + curr) % mod
			print(ans)


import sys
import numpy as np
mod = 10 ** 9 + 7

def gcd(p, q):
	if q == 0:
		return (p, 1, 0)
	(d, b, a) = gcd(q, p % q)
	return (d, a, b - p // q * a)

def inv(x):
	return gcd(mod, x)[2] % mod
mx = 10 ** 5 + 1
fact = np.ones(mx, dtype=np.int64)
ifact = np.ones(mx, dtype=np.int64)
for i in range(2, mx):
	fact[i] = fact[i - 1] * i % mod
	ifact[i] = ifact[i - 1] * inv(i) % mod

def choose(a, b):
	if b > a:
		return 0
	return fact[a] * ifact[a - b] % mod * ifact[b] % mod

def solve(n, m, k):
	if m > 0:
		return sum((choose(n - m, i) for i in range(k + 1))) % mod
	return sum((choose(n, i) for i in range(k, -1, -2))) % mod
f = sys.stdin
t = int(f.readline())
for i in range(t):
	(n, k) = map(int, f.readline().split())
	m = sum((1 for z in map(int, f.readline().split()) if z == 0))
	print(solve(n, m, k))


def gcd(a, b):
	if a < b:
		(q, w, e) = gcd(b, a)
		return (q, e, w)
	elif b == 0:
		return (a, 1, 0)
	else:
		(x, y, z) = gcd(b, a % b)
		return (x, z, y - z * (a // b))

def a(n, k, w):
	if w == 0:
		if k > n:
			op = (k - n) // 2 + (k - n) % 2
			k -= op * 2
		i = k % 2
		ans = 0
		if i == 0:
			c = 1
		else:
			c = n
		ans += c
		while i < k:
			(k1, k2) = (gcd(i + 1, 1000000007)[1], gcd(i + 2, 1000000007)[1])
			c *= (n - i) * (n - i - 1) * k1 * k2
			c = c % 1000000007
			i += 2
			ans = (ans + c) % 1000000007
		return ans
	elif k >= n - w:
		return 2 ** (n - w) % 1000000007
	else:
		n -= w
		ans = 0
		c = 1
		ans += c
		i = 1
		while i <= k:
			kkk = gcd(i, 1000000007)[1]
			c *= (n - i + 1) * kkk
			c = c % 1000000007
			i += 1
			ans = (ans + c) % 1000000007
		return ans
t = int(input())
while t != 0:
	t -= 1
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	w = l.count(0)
	print(a(n, k, w))


N = 10 ** 5 + 5
M = 10 ** 9 + 7
F = [0] * N
IF = [0] * N

def init():
	F[0] = IF[0] = 1
	for i in range(1, N):
		F[i] = F[i - 1] * i % M
		IF[i] = pow(F[i], M - 2, M)

def C(n, r):
	ans = F[n] * IF[r] * IF[n - r] % M
	return ans

def solveZero(n, k):
	ans = 0
	if k >= n:
		ans = pow(2, n, M)
	else:
		for i in range(k, -1, -1):
			ans += C(n, i)
	return ans % M

def solveNonZero(n, k):
	if k > n:
		if (k + n) % 2 == 0:
			k = n
		else:
			k = n - 1
	ans = 0
	for i in range(k, -1, -2):
		ans += C(n, i)
	return ans % M
init()
t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	zero = 0
	for i in a:
		if i == 0:
			zero += 1
	print(solveZero(n - zero, k) if zero else solveNonZero(n, k))


M = 1000000007
A = [pow(i, M - 2, M) for i in range(0, 100001)]
t = int(input())
while t > 0:
	t -= 1
	count = 0
	(n, k) = map(int, input().strip().split())
	L = list(map(int, input().strip().split()))
	for l in L:
		if l == 0:
			count += 1
	if count == 0:
		if k % 2 == 0:
			ans = 1
			i = 2
			cur = 1
		else:
			ans = n
			i = 3
			cur = n
		while i <= n and i <= k:
			cur = cur * (n - i + 1) * (n - i + 2) * (A[i] * A[i - 1]) % M % M
			ans = (ans + cur) % M
			i += 2
	else:
		ans = 1
		cur = 1
		i = 1
		n -= count
		while i <= n and i <= k:
			cur = cur * (n - i + 1) * A[i] % M
			ans = (ans + cur) % M
			i += 1
	print(ans)


mod = 1000000007
P = [pow(i, mod - 2, mod) for i in range(100001)]
T = int(input())
for t in range(T):
	(N, K) = map(int, input().strip().split())
	A = list(map(int, input().strip().split()))
	zero = A.count(0)
	if zero == 0:
		jump = 2
		start = 2
		ans = 1
		if K & 1:
			start = 3
			ans = N
		cur = ans
		for i in range(start, min(N, K) + 1, jump):
			nxt = cur * (N - i + 1) * (N - i + 2) * P[i] * P[i - 1] % mod
			ans = (ans + nxt) % mod
			cur = nxt
	else:
		jump = 1
		N -= zero
		start = 1
		ans = 1
		cur = 1
		for i in range(start, min(N, K) + 1, jump):
			nxt = cur * (N - i + 1) * P[i] % mod
			ans = (ans + nxt) % mod
			cur = nxt
	ans %= mod
	print(ans)


mod = 10 ** 9 + 7
lim = 10 ** 5
powm = [pow(i, mod - 2, mod) for i in range(lim + 1)]
t = int(input())
ip = lambda : [int(i) for i in input().split()]
for _ in range(t):
	(n, k) = ip()
	L = ip()
	zcount = L.count(0)
	n = n - zcount
	C = [1 for _ in range(n + 1)]
	for i in range(n):
		C[i + 1] = C[i] * (n - i) % mod * powm[i + 1] % mod
	if zcount > 0:
		ans = sum((C[i] for i in range(min(n, k) + 1))) % mod
	else:
		ans = sum((C[i] for i in range(k % 2, min(n, k) + 1, 2))) % mod
	print(ans)


f = [1]
m = 1000000007
inv = [0, 1]
for i in range(2, 100005):
	inv.append(m - m // i * inv[m % i] % m)
f_inv = [1]
for i in range(1, 100005):
	f.append(f[i - 1] * i % m)
for i in range(1, 100005):
	f_inv.append(f_inv[i - 1] * inv[i] % m)

def comb(a, b):
	return f[a] * f_inv[b] % m * f_inv[a - b] % m
for t in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	n1 = n
	for i in a:
		if i == 0:
			n1 -= 1
	if n == n1:
		if k % 2 == 0:
			j = 0
			sum = 1
		else:
			j = 1
			sum = n
		for i in range(j + 2, k + 1, 2):
			if i > n:
				break
			sum = (sum + comb(n, i)) % m
	else:
		sum = com = 1
		for i in range(1, k + 1):
			if i > n1:
				break
			sum = (sum + comb(n1, i)) % m
	print(sum % m)


mod = 10 ** 9 + 7
MOD = mod
fuck_torial = [1]
i = 1
mul = 1
inv = [1, 1]
fact_inv = [1]
for i in range(2, 10 ** 5 + 1):
	inv.append(MOD - MOD // i * inv[MOD % i] % MOD)
for i in range(1, 10 ** 5 + 1):
	fuck_torial.append(fuck_torial[i - 1] * i % MOD)
for i in range(1, 10 ** 5 + 1):
	fact_inv.append(fact_inv[i - 1] * inv[i] % MOD)

def ncr(a, b):
	return fuck_torial[a] * fact_inv[b] % MOD * fact_inv[a - b] % MOD
for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	cnt_zero = 0
	for i in arr:
		if i == 0:
			cnt_zero += 1
	if cnt_zero > 0:
		arr = [i for i in range(0, min(n - cnt_zero, k) + 1)]
		n -= cnt_zero
	elif k % 2 != 0:
		arr = [i for i in range(1, min(n, k) + 1, 2)]
	else:
		arr = [i for i in range(0, min(n, k) + 1, 2)]
	sumi = 0
	for i in arr:
		sumi += ncr(n, i)
	print(sumi % mod)