You are given an array A of N integers and an integer K. Find the number of (possibly empty) [subsequences] of A such that no two elements in the subsequence have a sum that is divisible by K.

Two subsequences are considered distinct if they are made up of different indices. For example, A = [1, 2, 1, 2] contains [1, 2] as a subsequence three times, and all 3 must be counted separately in the answer.

More formally,
Let S = \{x_{1}, x_{2}, \ldots, x_{m}\} be a (possibly empty) set such that 1 ≤ x_{1} < x_{2} < \ldots < x_{m} ≤ N.
S is said to be *good* if A_{x_{i}} + A_{x_{j}} is not divisible by K for any 1 ≤ i < j ≤ m. In particular, any subsequence of size ≤ 1 is *good*.
Your task is to count the number of *good* sets.

Since the answer can be very large, print it modulo 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 two lines of input.
- The first line of each test case contains two space separated integers, N and K.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N}

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

For each test case, output on a new line number of subsequences satisfying the condition, modulo 10^{9} + 7.

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

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ K ≤ 5 \cdot 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- The sum of $N$ and $K$ over all test cases won't exceed $10^{6}$.

----- Sample Input 1 ------ 
3
3 4
4 5 7
5 4
1 2 3 4 5
5 3
1 2 3 4 5
----- Sample Output 1 ------ 
6
20
14
----- explanation 1 ------ 
Test case $1$: Here, $K = 4$. There are $8$ subsequences of the array, and they are considered as follows:
- $[]$: the empty subsequence. It satisfies the condition.
- $[4], [5], [7]$: size $1$ subsequences, all are good.
- $[4, 5]$: good, because $4+5 = 9$ is not a multiple of $4$
- $[4, 7]$: good, because $4+7 = 11$ is not a multiple of $4$
- $[5, 7]$: not good, because $5+7=12$ is a multiple of $4$.
- $[4, 5, 7]$: not good, again because it contains $5$ and $7$.

So, $6$ of the subsequences are good.

Difficulty: VERY_HARD
Tags: Combinatorics

Mathematics

Starter code:

Solutions:
import collections
MOD = 10 ** 9 + 7

def mod_pow(a, b):
	if b == 0:
		return 1
	return mod_pow(a * a % MOD, b // 2) if b % 2 == 0 else a * mod_pow(a * a % MOD, b // 2) % MOD
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	freqs = collections.Counter([a % K for a in A])
	ans = freqs[0] + 1
	for i in range(1, (K + 1) // 2):
		ans = ans * (mod_pow(2, freqs[i]) + mod_pow(2, freqs[K - i]) - 1) % MOD
	if K % 2 == 0:
		ans = ans * (freqs[K // 2] + 1) % MOD
	print(ans)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	return input().strip()

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

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))
mod = 10 ** 9 + 7
ans = []
for _ in range(inp()):
	(N, K) = inlt()
	A = invr()
	an = 1
	f = {}
	for a in A:
		r = a % K
		if r in f:
			f[r] += 1
		else:
			f[r] = 1
	if 0 in f:
		r = f.pop(0)
		an *= r + 1
	if K % 2 == 0 and K // 2 in f:
		r = f.pop(K // 2)
		an *= r + 1
	an %= mod
	while f:
		(x, fx) = f.popitem()
		m = pow(2, fx, mod)
		if K - x in f:
			fx = f.pop(K - x)
			m += pow(2, fx, mod) - 1
		an = an * m % mod
	ans.append(an)
outplt(ans)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	return input().strip()

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

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))

def solve(N, K, A):
	an = 1
	rem = [0] * K
	for a in A:
		rem[a % K] += 1
	for x in range(K // 2 + 1):
		if 2 * x in [0, K]:
			an = an * (rem[x] + 1) % mod
		else:
			an = an * (pow(2, rem[x], mod) + pow(2, rem[K - x], mod) - 1) % mod
	return an
mod = 10 ** 9 + 7
ans = []
for _ in range(inp()):
	(N, K) = inlt()
	A = invr()
	ans.append(solve(N, K, A))
outplt(ans)


from collections import Counter

def simple_array(array, k):
	counter = Counter((x % k for x in array))
	singles = []
	pairs = []
	zeros = counter[0]
	mids = counter[k // 2] if k % 2 == 0 else 0
	for key in counter:
		if key == 0:
			continue
		c_key = (k - key) % k
		if c_key in counter:
			if key == c_key:
				continue
			if key <= k // 2:
				pairs.append((counter[key], counter[c_key]))
		else:
			singles.append(counter[key])
	acc = 1
	for single in singles:
		acc *= 2 ** single
	for pair in pairs:
		acc = acc * (2 ** pair[0] - 1) + acc * (2 ** pair[1] - 1) + acc
	if zeros > 0:
		acc *= zeros + 1
	if mids > 0:
		acc *= mids + 1
	return acc % (10 ** 9 + 7)
for _ in range(int(input())):
	(_, k) = map(int, input().split())
	array = list(map(int, input().split()))
	p = simple_array(array, k)
	print(p)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	list1 = [0] * k
	for i in a:
		a = i % k
		list1[a] += 1
	sum = 1
	for i in range(k // 2 + 1):
		if i == 0 or i == k / 2:
			sum *= list1[i] + 1
		else:
			sum *= 2 ** list1[i] + 2 ** list1[k - i] - 1
	print(sum % (10 ** 9 + 7))


t = int(input())
d = 0
while t > d:
	(n, k) = map(int, input().split())
	n1 = list(map(int, input().split()))
	j = [0] * k
	s = 1
	for i in n1:
		a = i % k
		j[a] += 1
	for i in range(k // 2 + 1):
		if i == 0 or i == k / 2:
			s *= j[i] + 1
		else:
			s *= 2 ** j[i] + (2 ** j[k - i] - 1)
	print(s % (10 ** 9 + 7))
	d += 1


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	list1 = [0] * K
	for i in A:
		a = i % K
		list1[a] += 1
	ans = 1
	for i in range(K // 2 + 1):
		if i == 0 or i == K / 2:
			ans *= list1[i] + 1
		else:
			ans *= 2 ** list1[i] + 2 ** list1[K - i] - 1
	print(ans % (10 ** 9 + 7))


T = int(input())
for z in range(T):
	(Nlen, Kel) = map(int, input().split())
	A = list(map(int, input().split()))
	l = [0] * Kel
	i = 0
	while i < Nlen:
		a = A[i] % Kel
		l[a] += 1
		i += 1
	ans = 1
	h = 0
	while h <= Kel // 2:
		if h == 0 or h == Kel / 2:
			ans *= l[h] + 1
		else:
			ans *= 2 ** l[h] + (2 ** l[Kel - h] - 1)
		h += 1
	print(ans % (10 ** 9 + 7))


mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	freq = [0] * k
	for x in a:
		freq[x % k] += 1
	ans = 1
	for i in range(k):
		if i == 0 or 2 * i == k:
			ans *= 1 + freq[i]
		else:
			if i > k - i:
				break
			ans *= pow(2, freq[i], mod) + pow(2, freq[k - i], mod) - 1
		ans %= mod
	print(ans % mod)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	freq = [0] * k
	for i in l:
		freq[i % k] += 1
	ans = 1
	for i in range(k // 2 + 1):
		if i == 0 or i == k / 2:
			ans *= 1 + freq[i]
		else:
			ans *= 2 ** freq[i] + 2 ** freq[k - i] - 1
	mod = 10 ** 9 + 7
	print(ans % mod)


k = int(input())
for l in range(k):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	num_arr = [0 for i in range(k)]
	for i in range(len(arr)):
		temp = arr[i] % k
		num_arr[temp] += 1
	mod = 1000000007
	f_ans = 1
	for i in range((k + 2) // 2):
		if i == 0:
			f_ans *= num_arr[0] + 1
			continue
		if 2 * i == k:
			f_ans = f_ans * (num_arr[i] + 1) % mod
			continue
		f_ans = f_ans * (pow(2, num_arr[i], mod) + pow(2, num_arr[k - i], mod) - 1) % mod
	print(f_ans % 1000000007)


from collections import Counter

def modMul(a, b, mod):
	return a % mod * b % mod % mod

def solve():
	(n, k) = map(int, input().split())
	m = Counter(map(lambda x: int(x) % k, input().split()))
	ans = 1
	mod = 1000000007
	for i in range(0, k // 2 + 1):
		a = m[i]
		if (i == k - i or i == 0) and a != 0:
			ans = modMul(ans, a + 1, mod)
		else:
			b = m[k - i]
			temp = (pow(2, a, mod) + pow(2, b, mod) - 1) % mod
			ans = modMul(ans, temp, mod)
	print(ans)
tc = int(input())
for _ in range(tc):
	solve()


t = int(input())
mod = 10 ** 9 + 7
for g in range(t):
	f = list(map(int, input().split()))
	array = list(map(int, input().split()))
	n = f[0]
	k = f[1]
	new = [0] * k
	for j in array:
		new[j % k] += 1
	product = 1
	for i in range(k):
		if i == 0 or 2 * i == k:
			product *= new[i] + 1
			product = product % mod
		elif i > k - i:
			break
		else:
			product *= 2 ** new[i] % mod + 2 ** new[k - i] % mod - 1
			product = product % mod
	print(product % mod)


def solve(a, n, k):
	freq = [0] * k
	for i in range(n):
		freq[a[i] % k] += 1
	ans = 1
	for i in range(k):
		if i == 0 or i * 2 == k:
			ans *= freq[i] + 1
		elif i > k - i:
			break
		else:
			ans *= 2 ** freq[i] % mod + 2 ** freq[k - i] % mod - 1
		ans = ans % mod
	return ans % mod
mod = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(solve(a, n, k))


from sys import stdin, stdout
from collections import defaultdict as dd
stdint = lambda : int(stdin.readline())
mul = lambda : map(int, stdin.readline().strip().split())
seq = lambda : list(map(int, stdin.readline().strip().split()))
for _ in range(stdint()):
	(n, k) = mul()
	nums = seq()
	m = dd(int)
	for num in nums:
		idx = num % k
		m[idx] += 1
	ans = 1
	mod = int(1000000000.0) + 7
	for i in range(1, (k + 1) // 2):
		a = m[i]
		b = m[k - i]
		if a > 0 or b > 0:
			temp = (pow(2, a, mod) + pow(2, b, mod) - 1) % mod
			ans *= temp
			ans = ans % mod
	if m[0] > 0:
		ans *= m[0] + 1
		ans = ans % mod
	if k % 2 == 0 and m[k // 2] > 0:
		ans *= m[k // 2] + 1
		ans = ans % mod
	print(ans)


import math
mod = 1000000007

def power(a, b):
	if b == 0:
		return 1
	if b == 1:
		return a
	res = 1
	if b % 2 == 1:
		res = a
	s = power(a, b / 2)
	s = s * s % mod
	s = s * res % mod
	return s
for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	dp = [0] * k
	for i in range(len(arr)):
		dp[arr[i] % k] += 1
	c = math.ceil(len(dp) / 2)
	ans = 1
	for j in range(k):
		if j == 0 or 2 * j == k:
			ans *= 1 + dp[j]
		else:
			if j > k - j:
				break
			c1 = k - j
			ans = ans * (pow(2, dp[j]) + pow(2, dp[c1]) - 1)
	print(ans % mod)


from sys import stdin
input = stdin.readline
MODULO = 10 ** 9 + 7

def solve(N, K, A):
	frequency = [0] * K
	for a in A:
		frequency[a % K] += 1
	count = (1 + frequency[0]) % MODULO
	if K % 2 == 0:
		c = (1 + frequency[K // 2]) % MODULO
		count = count * c % MODULO
	for i in range(1, (K + 1) // 2):
		c = (pow(2, frequency[i], MODULO) + pow(2, frequency[K - i], MODULO) - 1) % MODULO
		count = count * c % MODULO
	return count
T = int(input().strip())
for problem in range(1, T + 1):
	(N, K) = [int(x) for x in input().strip().split()]
	A = [int(x) for x in input().strip().split()]
	print(solve(N, K, A))


import sys
f = (map(int, s.split()) for s in sys.stdin)
next(f)
for ((n, k), a) in zip(f, f):
	c = [0] * k
	for x in a:
		c[x % k] += 1
	k += 1
	m = k // 2
	r = c[0] + 1
	if k % 2:
		r *= c[m] + 1
	for i in range(1, m):
		r = r * (2 ** c[i] + 2 ** c[-i] - 1) % (10 ** 9 + 7)
	print(r)


from collections import Counter
MOD = 10 ** 9 + 7
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	d = Counter()
	for n in A:
		d[n % K] += 1
	res = 1
	for i in range(1, (K + 1) // 2):
		a = d[i]
		b = d[K - i]
		if a or b:
			res *= ((1 << a) % MOD + (1 << b) % MOD - 1) % MOD
			res %= MOD
	if d[0]:
		res *= d[0] + 1
		res %= MOD
	if K % 2 == 0 and d[K // 2]:
		res *= d[K // 2] + 1
		res %= MOD
	print(res)


def getKey(dic, key):
	if key in dic:
		return dic[key]
	else:
		return 0

def solve():
	(n, k) = [int(i) for i in input().split(' ') if i]
	vec = [int(i) for i in input().split(' ') if i]
	remainders = {}
	for i in vec:
		rm = i % k
		if rm in remainders:
			remainders[rm] += 1
		else:
			remainders[rm] = 1
	ans = 1
	seen = set()
	for rm in remainders:
		if rm in seen:
			continue
		x = 1
		seen.add(rm)
		if k == 2 * rm or rm == 0:
			x += remainders[rm]
		else:
			x += 2 ** remainders[rm] - 1
			other = getKey(remainders, k - rm)
			x += 2 ** other - 1
			seen.add(k - rm)
		ans *= x
	print(ans % (10 ** 9 + 7))
t = int(input())
for i in range(t):
	solve()


MOD = 10 ** 9 + 7
from collections import Counter
for test in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	temp = [i % k for i in arr]
	cnt = dict(Counter(temp))
	ans = 1
	vis = {}
	for ele in cnt:
		if ele == 0 or 2 * ele == k:
			ans *= cnt[ele] + 1
		else:
			if vis.get(ele, -1) == 1:
				continue
			elif cnt.get(k - ele, -1) != -1:
				vis[ele] = 1
				vis[k - ele] = 1
				ans *= pow(2, cnt[ele], MOD) + pow(2, cnt[k - ele], MOD) - 1
			else:
				vis[ele] = 1
				ans *= pow(2, cnt[ele], MOD)
			ans %= MOD
	print(ans % MOD)


from sys import setrecursionlimit
mod_ = 10 ** 9 + 7
setrecursionlimit(10 ** 7)

def drive():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	count = 1
	cnt = [0] * k
	for i in a:
		cnt[i % k] += 1
	for i in range(k // 2 + 1):
		if i == 0 or i + i == k:
			count *= 1 + cnt[i]
		else:
			count *= pow(2, cnt[i], mod_) + pow(2, cnt[k - i], mod_) - 1
		count %= mod_
	print(count)
t = int(input())
for _ in range(t):
	drive()


from collections import Counter

def readlist():
	return list(map(int, input().split()))

def readint():
	return int(input())

def printbool(result: bool):
	print('YES') if result else print('NO')
mod = 10 ** 9 + 7
T = readint()
for _ in range(T):
	(N, K) = readlist()
	A = readlist()
	lookup = Counter((a % K for a in A))
	result = lookup[0] + 1
	if K % 2 == 0:
		result *= lookup[K // 2] + 1
	for i in range(1, (K + 1) // 2):
		result *= pow(2, lookup[i], mod) + pow(2, lookup[K - i], mod) - 1
		result %= mod
	result %= mod
	print(result)


MOD = 10 ** 9 + 7
for tc in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		if i % k not in d:
			d[i % k] = 1
		else:
			d[i % k] += 1
	s = 1
	if 0 in d:
		s *= d[0] + 1
	if k % 2 == 0 and k // 2 in d:
		s *= 1 + d[k // 2]
	x = -1
	if k % 2 == 0:
		x = k // 2
	else:
		x = k // 2 + 1
	for i in range(1, x):
		if i in d and k - i in d:
			s *= (pow(2, d[i], MOD) + pow(2, d[k - i], MOD) - 1) % MOD
		elif i in d:
			s *= pow(2, d[i], MOD) % MOD
		elif k - i in d:
			s *= pow(2, d[k - i], MOD) % MOD
	print(int(s % MOD))


MOD = 10 ** 9 + 7
from collections import Counter
from math import ceil
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [i % k for i in map(int, input().split())]
	c = Counter(a)
	remaining = n - c[0]
	ans = (pow(2, c[0], MOD) - 1 - c[0]) * pow(2, remaining, MOD) % MOD
	onlyone = c[0] + 1
	if k % 2 == 0:
		remaining -= c[k // 2]
		ans = (ans + (pow(2, c[k // 2], MOD) - 1 - c[k // 2]) * onlyone * pow(2, remaining, MOD)) % MOD
		onlyone = onlyone * (c[k // 2] + 1) % MOD
	for i in range(1, ceil(k / 2)):
		remaining -= c[i] + c[k - i]
		ans = (ans + (pow(2, c[i], MOD) - 1) * (pow(2, c[k - i], MOD) - 1) * onlyone * pow(2, remaining, MOD)) % MOD
		onlyone = onlyone * (pow(2, c[i], MOD) - 1 + (pow(2, c[k - i], MOD) - 1) + 1) % MOD
	print((pow(2, n, MOD) - ans) % MOD)


m = 10 ** 9 + 7
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ayush = [0 for i in range(k)]
	for i in range(n):
		ayush[a[i] % k] += 1
	chaurasia = 1
	if ayush[0] >= 1:
		chaurasia *= ayush[0] + 1
	for i in range(1, k // 2 + 1):
		if k % 2 == 0 and i == k // 2:
			if ayush[i] != 0:
				chaurasia *= ayush[i] + 1
			chaurasia = chaurasia % m
			continue
		if ayush[i] == 0 and ayush[k - i] == 0:
			continue
		if ayush[i] == 0:
			chaurasia *= 2 ** ayush[k - i]
			chaurasia = chaurasia % m
			continue
		if ayush[k - i] == 0:
			chaurasia *= 2 ** ayush[i]
			chaurasia = chaurasia % m
			continue
		chaurasia *= 2 ** ayush[i] + 2 ** ayush[k - i] - 1
		chaurasia = chaurasia % m
	print(chaurasia)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	arr1 = list(map(int, input().split()))
	arr2 = [0] * k
	for i in range(n):
		arr2[arr1[i] % k] += 1
	Sum = 1
	if arr2[0] >= 1:
		Sum *= arr2[0] + 1
	for i in range(1, int(k / 2 + 1)):
		if k % 2 == 0 and i == int(k / 2):
			if arr2[i] != 0:
				Sum *= arr2[i] + 1
			Sum %= 1000000007
			continue
		if arr2[i] == 0 and arr2[k - i] == 0:
			continue
		if arr2[i] == 0:
			Sum *= pow(2, arr2[k - i])
			Sum %= 1000000007
			continue
		if arr2[k - i] == 0:
			Sum *= pow(2, arr2[i])
			Sum %= 1000000007
			continue
		Sum *= pow(2, arr2[i]) + pow(2, arr2[k - i]) - 1
		Sum %= 1000000007
	print(Sum)


beeg = 10 ** 9 + 7
aa = [1, 2, 4]

def aaa(n):
	if n < len(aa):
		return aa[n]
	else:
		for i in range(len(aa), n + 1):
			aa.append(aa[-1] * 2 % beeg)
		return aa[-1]
for tea in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	count = dict()
	if k == 1:
		print(n + 1)
		continue
	for i in range(k):
		count[i] = 0
	for i in a:
		awa = i % k
		count[awa] += 1
	l = 1
	r = k - 1
	ans = 1
	while l < r:
		ans *= aaa(count[l]) + aaa(count[r]) - 1
		ans = ans % beeg
		l += 1
		r -= 1
	if count[0] >= 1:
		ans = ans * (count[0] + 1) % beeg
	if k % 2 == 0 and count[k // 2] >= 1:
		ans = ans * (count[k // 2] + 1) % beeg
	print(ans % beeg)


import math
mod = pow(10, 9) + 7
T = int(input())
for testNum in range(T):
	(N, K) = map(int, input().split(' '))
	nums = list(map(int, input().split(' ')))
	counts = {}
	for i in range(K):
		counts[i] = 0
	for val in nums:
		counts[val % K] += 1
	total = 1
	for i in range(1, math.ceil(K / 2)):
		c = counts[i]
		c2 = counts[K - i]
		total *= pow(2, c) + pow(2, c2) - 1
		total %= mod
	if K % 2 == 0:
		total *= 1 + counts[K / 2]
		total %= mod
	total *= counts[0] + 1
	total %= mod
	print(total)


import sys, math

def get_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())
mod = 10 ** 9 + 7

def countKdivPairs(A, n, K):
	freq = [0] * K
	for i in range(n):
		freq[A[i] % K] += 1
	val1 = freq[0] + 1
	if K % 2 == 0:
		val2 = freq[K // 2] + 1
	else:
		val2 = 1
	ans = 1
	for i in range(1, (K + 1) // 2):
		ans = ans * (pow(2, freq[i], mod) + pow(2, freq[K - i], mod) - 1) % mod
	fans = ans * val1 * val2 % mod
	return fans
t = int(sys.stdin.readline())
for t2 in range(t):
	(n, k) = get_ints()
	a = get_arr()
	ans = countKdivPairs(a, n, k)
	print(ans)