Read problems statements in Mandarin Chinese  and Russian. 
Sereja have an array that consist of n integers a[1], a[2], ..., a[n]. Now Sereja want to delete some(possible none, but not all) elements from the array, such that arithmetical mean of all remaining numbers will as big as possible.
Help Sereja, find number of ways to delete numbers.

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

First line contain integer T - number of testcases. T tests follow. First line of each testcase contain integer n. Next line contain n integers a[1], a[2], ..., a[n].
 
------ Output ------ 

For each testcase print the answer modulo 10^{9}+7.
 
------ Constraints ------ 

1 ≤ T ≤ 10
1 ≤ n ≤ 10^{5}
1 ≤ a[i] ≤ 10^{5}

------ Note ------ 

Test #0-1(25 points) n  ≤ 20
Test #2(25 points) n  ≤ 1000
Test #3-4(50 points) n  ≤ 100000

----- Sample Input 1 ------ 
2
1
1
4
1 2 1 2
----- Sample Output 1 ------ 
1
3

Source: codechef | Difficulty: MEDIUM
Tags: Combinatorics

Mathematics


Solutions:
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	ma = max(a)
	for i in a:
		if i == ma:
			count += 1
	print((2 ** count - 1) % (10 ** 9 + 7))


from collections import Counter
mod = 10 ** 9 + 7
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = dict(Counter(l))
	a = d[max(d.keys())]
	print((pow(2, a, mod) - 1) % mod)


mod = 1000000007
t = int(input())
for tc in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = max(a)
	c = 0
	for i in a:
		if i == m:
			c += 1
	ans = (pow(2, c, mod) - 1) % mod
	print(ans)


for _ in range(int(input())):
	n = int(input())
	nli = list(map(int, input().split()))
	md = 10 ** 9 + 7
	mx = max(nli)
	cnt = nli.count(mx)
	ans = (pow(2, cnt) - 1) % md
	print(ans)


mod = 1000000007
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = max(a)
	c = 0
	for i in a:
		if i == m:
			c += 1
	print(pow(2, c, mod) - 1)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = max(a)
	c = 0
	for j in a:
		if j == m:
			c += 1
	print(pow(2, c, 1000000007) - 1)


from collections import Counter
import string
import math
import bisect
import sys
from fractions import Fraction

def array_int():
	return [int(i) for i in sys.stdin.readline().split()]

def vary(arrber_of_variables):
	if arrber_of_variables == 1:
		return int(sys.stdin.readline())
	if arrber_of_variables >= 2:
		return map(int, sys.stdin.readline().split())

def makedict(var):
	return dict(Counter(var))
testcases = vary(1)
for _ in range(testcases):
	n = vary(1)
	num = array_int()
	ct = num.count(max(num))
	print(pow(2, ct, 10 ** 9 + 7) - 1)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	m = max(arr)
	c = 0
	for i in arr:
		if i == m:
			c += 1
	print(pow(2, c, 1000000007) - 1)


result = []
for _ in range(int(input())):
	x = int(input())
	array = list(map(int, input().split()))
	array.sort()
	point = 0
	for i in range(len(array)):
		if array[len(array) - i - 1] == array[-1]:
			point += 1
		else:
			break
	result.append((2 ** point - 1) % (10 ** 9 + 7))
for i in result:
	print(i)


try:
	result = []
	mod = 10 ** 9 + 7
	for _ in range(int(input())):
		x = int(input())
		array = list(map(int, input().split()))
		array.sort()
		point = 0
		for i in range(len(array)):
			if array[len(array) - i - 1] == array[-1]:
				point += 1
			else:
				break
		result.append(pow(2, point, mod) - 1)
	for i in result:
		print(i)
except:
	pass


mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	ss = 0
	k = a[-1]
	i = n - 1
	while a[i] == k and i >= 0:
		ss += 1
		i -= 1
	print(pow(2, ss, mod) - 1)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print((pow(2, a.count(max(a))) - 1) % (10 ** 9 + 7))


for j in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	a = x.count(max(x))
	b = 2 ** a - 1
	print(b % 1000000007)


e = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	x = max(l)
	x = l.count(x)
	ans = (pow(2, x, e) - 1) % e
	print(ans)


import math
M = 10 ** 9 + 7
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	k = max(a)
	f = 0
	for j in range(n):
		if k == a[j]:
			f += 1
	g = pow(2, f)
	g -= 1
	print(g % M)


for u in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = l.count(max(l))
	print((2 ** m - 1) % (10 ** 9 + 7))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	mc = a.count(max(a))
	print((2 ** mc - 1) % (10 ** 9 + 7))


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	count = 0
	count1 = 0
	m = 10 ** 9 + 7
	for i in l:
		if i != l[-1]:
			count += 1
		else:
			count1 += 1
	a = (pow(2, count1, m) - 1 % m) % m
	print(a % m)


MOD = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	if n == 1:
		print(1)
	elif l.count(max(l)) == n:
		ans = pow(2, n, MOD) - 1
		ans = (ans + MOD) % MOD
		print(ans)
	else:
		m = max(l)
		cnt = 1
		maxicnt = l.count(m)
		cnt += pow(2, maxicnt, MOD) - 2
		print((cnt + MOD) % MOD)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().strip().split()))
	max1 = max(a)
	ct = 0
	for i in a:
		if i == max1:
			ct += 1
	print((2 ** ct - 1) % (10 ** 9 + 7))


mm = 10 ** 9 + 7
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = max(a)
	count = 0
	for i in a:
		if i == m:
			count += 1
	ans = 1
	for i in range(count):
		ans *= 2
		ans %= mm
	print(ans - 1)


for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	l.sort()
	i = n - 1
	count = 0
	while i >= 0 and l[i] == l[n - 1]:
		count += 1
		i = i - 1
	print(pow(2, count, 1000000007) - 1)


import math
T = int(input())
for t in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	M = A.count(max(A))
	print(int((2 ** M - 1) % 1000000007))


t = int(input())
for i in range(0, t):
	n = int(input())
	List = []
	list = input()
	finalList = list.split(' ')
	for i in finalList:
		a = int(i)
		List.append(a)
	List.sort()
	if n == 1:
		print('1')
	elif List[0] == List[n - 1]:
		print((2 ** n - 1) % 1000000007)
	else:
		count = 0
		temp = List[0]
		for i in range(0, n):
			if temp == List[i]:
				count += 1
			else:
				count = 1
				temp = List[i]
		print((2 ** count - 1) % 1000000007)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print((2 ** a.count(max(a)) - 1) % 1000000007)


a = []
t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	maxi = -1
	count = 0
	ans = 1
	for i in range(0, n):
		if a[i] > maxi:
			maxi = a[i]
	for i in range(0, n):
		if a[i] == maxi:
			count = count + 1
	while count > 0:
		ans = ans * 2 % 1000000007
		count = count - 1
	print(ans - 1)
	t = t - 1


for ti in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(a.count(max(a))):
		ans = (ans << 1 | 1) % 1000000007
	print(ans)


numCases = int(input())
for eachCase in range(numCases):
	numSize = int(input())
	numTup = tuple(map(int, input().split(' ')))
	(maxnum, maxcount) = (0, 0)
	for eachNum in numTup:
		if eachNum > maxnum:
			(maxnum, maxcount) = (eachNum, 1)
		elif eachNum == maxnum:
			maxcount += 1
	print((2 ** maxcount - 1) % 1000000007)


import sys
T = int(sys.stdin.readline().rstrip('\n'))
for t in range(T):
	sys.stdin.readline()
	array = [int(i) for i in sys.stdin.readline().rstrip('\n').split(' ')]
	N = array.count(max(array))
	print((2 ** N - 1) % (10 ** 9 + 7))


T = int(input())
for t in range(T):
	n = int(input())
	L = list(map(int, input().split()))
	x = max(L)
	i = L.count(x)
	p = pow(2, i, 10 ** 9 + 7)
	p -= 1
	if p < 0:
		p += 10 ** 9 + 7
	print(p)