There are N balls in a bag. Initially, the i^{th} ball has a number A_{i} on it.  

In one second, a ball with number k (k>1), dissociates into k balls, where each of the k balls has number (k-1) written on it.  
If k = 1, there is no change on the state of the ball. 

Find the number of balls in the bag after 10^{100} seconds. Since the final number of balls can be huge, output the answer 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 an integer N, denoting the number of balls in the bag.
- The next line contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N}, denoting the initial number written on the balls.

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

For each test case, output on a new line, the number of balls in the bag after 10^{100} seconds. Since the final number of balls can be huge, output the answer modulo 10^{9}+7.

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

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

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

----- Sample Output 1 ------ 
2
3
13

----- explanation 1 ------ 
Test case $1$: Initially, the balls in the bag are $\{2\}$.
- After $1$ second: The ball with number $2$ dissociates into two balls with number $1$. Thus, the bag looks like $\{1, 1\}$.

No more dissociation is possible after this. Thus, the final number of balls is $2$.

Test case $2$: Initially, the balls in the bag are $\{1, 2\}$.
- After $1$ second: The ball with number $2$ dissociates into two balls with number $1$. Thus, the final bag looks like $\{1, 1, 1\}$.

No more dissociation is possible after this. Thus, the final number of balls is $3$.

Test case $3$: Initially, the balls in the bag are $\{3, 1, 3\}$.
- After $1$ second: The balls with number $3$ dissociates into three balls with number $2$. Thus, the bag looks like $\{2, 2, 2, 1, 2, 2, 2\}$.
- After $2$ seconds: The balls with number $2$ dissociates into two balls with number $1$. Thus, the bag looks like $\{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1\}$.

No more dissociation is possible after this. Thus, the final number of balls is $13$.

Difficulty: MEDIUM
Tags: Mathematics

Starter code:

Solutions:
mod = 10 ** 9 + 7
cheat = [1] * (10 ** 6 + 1)
for i in range(1, 10 ** 6 + 1):
	cheat[i] = cheat[i - 1] * i % mod
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = Counter([int(x) for x in input().split()])
	ans = 0
	for i in a:
		ans += cheat[i] * a[i]
	print(ans % mod)


z = [1]
for i in range(1, 10 ** 6 + 1):
	z.append(z[i - 1] * i % (10 ** 9 + 7))
t = int(input())
for item in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	s = 0
	for i in arr:
		s = s + z[i]
	print(s % 1000000007)


t = int(input())
xfact = [1]
for i in range(1, 1000001):
	xfact.append(xfact[i - 1] * i % 1000000007)
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	val = 0
	for i in lst:
		val += xfact[i]
	print(val % 1000000007)


t = int(input())
fact = [1]
for i in range(1, 1000001):
	fact.append(fact[i - 1] * i % 1000000007)
for t in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	sum = 0
	for a in arr:
		sum += fact[a]
	print(sum % 1000000007)


from math import sqrt, ceil, floor, gcd, log2
import sys
from sys import stdin, stdout
from collections import Counter, defaultdict, OrderedDict, deque
from itertools import combinations, groupby
from time import time
from heapq import heappop, heappush, heapify
fac = [1] * (10 ** 6 + 1)
for i in range(1, len(fac)):
	fac[i] = fac[i - 1] * i % (10 ** 9 + 7)
for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	result = 0
	for i in s:
		result = result + fac[i]
	print(result % (10 ** 9 + 7))


fac = [1] * (10 ** 6 + 1)
for i in range(1, len(fac)):
	fac[i] = fac[i - 1] * i % (10 ** 9 + 7)
for _ in range(int(input())):
	n = int(input()) - 1
	s = list(map(int, input().split()))
	result = 0
	for i in s:
		result = result + fac[i]
	print(result % (10 ** 9 + 7))


MODULO = 1000000007
K_MAX = 1000001
T = int(input())
fact = [1]
for i in range(1, K_MAX):
	fact.append(fact[i - 1] * i % MODULO)
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	sum = 0
	for i in range(n):
		sum = (sum + fact[a[i]]) % MODULO
	print(sum)


d = [1]
for j in range(2, 1000000 + 1):
	d += [d[-1] * j % 1000000007]
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for x in a:
		ans += d[x - 1]
	print(ans % 1000000007)


d = [1]
for ii in range(2, 1000000 + 1):
	d += [d[-1] * ii % 1000000007]
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for xx in a:
		ans += d[xx - 1]
	print(ans % 1000000007)


l1 = [1]
for _ in range(1, 10 ** 6):
	l1.append(l1[_ - 1] * _ % 1000000007)
t = input()
for c in range(0, int(t)):
	n = int(input())
	l = list(map(int, input().split()))
	d = 0
	for _ in l:
		d += l1[_]
	print(d % 1000000007)


num_cases = int(input())
factorials = {}
for case in range(num_cases):
	input()
	balls = input().split()
	total = 0
	for ball in balls:
		n = int(ball)
		if n in factorials:
			total += factorials[n]
		else:
			factorial = 1
			for k in range(2, n + 1):
				factorial *= k
				factorial %= 1000000007
				factorials.update({k: factorial})
			total += factorial
		total %= 1000000007
	print(total)


dic = {1: 1, 2: 2, 3: 6, 4: 24}
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	mod = 1000000007
	ans = 0
	for e in a:
		if e in dic.keys():
			ans = (ans + dic[e]) % mod
			continue
		count = max(dic.keys())
		while True:
			dic[count + 1] = (count + 1) * dic[count] % mod
			count += 1
			if count == e:
				break
		ans = (ans + dic[e]) % mod
	print(ans)


l = []
mx = []
kl = []
tc = int(input())
for i in range(tc):
	n = int(input())
	k = list(map(int, input().split()))
	kl.append(k)
	mx.append(max(k))
d = {}
ff = 1
for kk in range(1, max(mx) + 1):
	d[kk] = ff % 1000000007
	ff = ff * (kk + 1)
	ff = ff % 1000000007
for i in range(tc):
	ans = 0
	for t in kl[i]:
		ans += d[t]
		ans % 1000000007
	print(ans % 1000000007)


mod = 10 ** 9 + 7
factorials = [0] * 10 ** 6
factorials[0] = factorials[1] = 1
for i in range(2, len(factorials)):
	factorials[i] = factorials[i - 1] * i % mod
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	ans = 0
	for i in range(len(A)):
		ans += factorials[A[i]]
		ans = ans % mod
	print(ans)


factorials = [1]
for i in range(1, 10 ** 6 + 1):
	factorials.append(factorials[i - 1] * i % 1000000007)
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	n = 0
	for x in l:
		n += factorials[x]
	print(n % 1000000007)


NN = 1000000007
store = [1] * 10 ** 6
for i in range(2, 10 ** 6):
	store[i] = store[i - 1] % NN * (i % NN) % NN
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	total = 0
	for i in arr:
		total += store[i] % NN
	print(int(total % NN))


f = [1]
for i in range(1, 10 ** 6):
	f.append(f[i - 1] * i % 1000000007)
for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	sum = 0
	for i in c:
		sum += f[i]
	print(sum % 1000000007)


aux = [0] * 1000001
aux[0] = 1
i = 1
for _ in range(1000000):
	aux[i] = aux[i - 1] * i % 1000000007
	i += 1
for _ in range(int(input())):
	n = int(input())
	ans = 0
	arr = list(map(int, input().split()))
	for i in range(n):
		ans = (ans + aux[arr[i]]) % 1000000007
	print(ans)


MOD = 10 ** 9 + 7
MAX = 10 ** 6 + 1
fac = [1, 1]
for i in range(2, MAX):
	fac += [fac[-1] * i % MOD]
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	res = 0
	for i in arr:
		res = (res + fac[i]) % MOD
	print(res)


dp = {}
dp[1] = 1
for i in range(2, 1000000 + 1):
	dp[i] = dp[i - 1] * i % (10 ** 9 + 7)
t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	s = 0
	for i in arr:
		s = (s + dp[i]) % (10 ** 9 + 7)
	print(s % (10 ** 9 + 7))
	t -= 1


dp = {}
dp[1] = 1
for j in range(2, 1000000 + 1):
	dp[j] = dp[j - 1] * j % (10 ** 9 + 7)
for i in range(int(input())):
	a = int(input())
	l = [int(x) for x in input().split()]
	c = max(l)
	ans = 0
	for j in l:
		ans = ans + dp[j]
	print(ans % (10 ** 9 + 7))


A = {}
A[1] = 1
M = pow(10, 9) + 7
for i in range(2, 1000001):
	A[i] = A[i - 1] * i % M
T = int(input())
for i in range(T):
	N = int(input())
	B = list(map(int, input().split()))
	sum = 0
	for k in B:
		sum += A[k]
	print(sum % M)


x = 1000000007
d = dict()

def factorial(n):
	temp = 1
	for i in range(1, n + 1):
		temp *= i
		temp = temp % x
		d[i] = temp
	return temp
t = int(input())
for _ in range(t):
	answer = 0
	n = int(input())
	arr = list(map(int, input().strip().split()))
	for i in arr:
		if i in d:
			answer += d[i] % x
		else:
			temp2 = factorial(i)
			answer += temp2 % x
		answer = answer % x
	print(answer)


import math
f = []
x = 1
for i in range(1, 1000001):
	x = x * i % 1000000007
	f.append(x)
for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	ans = 0
	for i in l:
		ans = (ans % 1000000007 + f[i - 1]) % 1000000007
	print(ans)


f = [1]
for i in range(1, 10 ** 6 + 1):
	f.append(i * f[i - 1])
	f[i] = f[i] % (10 ** 9 + 7)
for i in range(int(input())):
	balls = int(input())
	num = [int(i) for i in input().split(' ')]
	count = 0
	for j in num:
		count = count + f[int(j)]
	print(count % (10 ** 9 + 7))


t = int(input())
d = {}
s = 1
for x in range(1, 1000001):
	s *= x
	s = s % 1000000007
	d[x] = s
for i in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	su = 0
	for x in l:
		su += d[x]
	print(su % 1000000007)


k = 10 ** 9 + 7
d = {1: 1}
for i in range(2, 1000001):
	d[i] = i % k * d[i - 1] % k
t = int(input())
for j in range(t):
	n = int(input())
	s = 0
	l = [int(x) for x in input().split()]
	for i in l:
		s += d[i] % k
	print(s % k)


f = [1]
for i in range(1, 10 ** 6 + 1):
	f.append(i * f[i - 1])
	f[i] = f[i] % (10 ** 9 + 7)
for i in range(int(input())):
	n = int(input())
	lst = input().split()
	count = 0
	for j in lst:
		count = count + f[int(j)]
	print(count % (10 ** 9 + 7))


facl = [1]
for i in range(1, 1000001):
	facl.append(i * facl[i - 1])
	facl[i] %= 1000000007
for test in range(int(input())):
	n = int(input())
	a = input().split()
	sum = 0
	for i in a:
		sum += facl[int(i)]
	print(sum % 1000000007)


ls = [1]
for i in range(1, 1000001):
	ls.append(i * ls[i - 1])
	ls[i] %= 1000000007
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	s = 0
	for i in a:
		s += ls[i]
	print(s % 1000000007)


n = 1000001
m = 1000000007
list2 = [0, 1]
for i in range(2, n):
	list2.append(list2[i - 1] * i % m)
for _ in range(int(input())):
	a = int(input())
	list1 = list(map(int, input().split(' ')[:a]))
	sum1 = 0
	for i in list1:
		if i != 1:
			b = list2[i]
			sum1 = sum1 + b
		else:
			sum1 = sum1 + 1
	print(sum1 % m)


fact = [1]
for i in range(1, 1000001):
	fact.append(i * fact[i - 1])
	fact[i] %= 1000000007
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	p = 0
	for i in l:
		p = p + fact[i]
	print(p % 1000000007)


fact = [1]
for k in range(1, 1000001):
	fact.append(k * fact[k - 1])
	fact[k] %= 1000000007
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	for u in range(n):
		ans += fact[l[u]]
	print(ans % 1000000007)


(mod, lookup, l) = (10 ** 9 + 7, dict(), 1)
for i in range(1, 10 ** 6 + 1):
	l = l * i % mod
	lookup[i] = l
for _ in range(int(input())):
	(n, ans) = (int(input()), 0)
	arr = list(map(int, input().split()))
	for i in arr:
		ans = (ans + lookup[i]) % mod
	print(ans)


dp = [0] * (10 ** 6 + 1)
dp[0] = 1
mod = 10 ** 9 + 7
for i in range(1, 10 ** 6 + 1):
	dp[i] = dp[i - 1] * i % mod
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	res = 0
	for i in l:
		res += dp[i] % mod
	print(res % mod)


data = [None] * (10 ** 6 + 1)
data[0] = 1
for i in range(1, 10 ** 6 + 1):
	data[i] = data[i - 1] % 1000000007 * i
t = int(input())
i = 0
while i < t:
	N = int(input())
	a = list(map(int, input().split()))
	count = 0
	for j in a:
		count = count + data[j]
	print(count % 1000000007)
	i = i + 1


mod = 1000000007
d = {1: 1}
for i in range(2, 10000001):
	d[i] = d[i - 1] % mod * i
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	for i in l:
		ans += d[i] % mod
	print(ans % mod)


mod = 10 ** 9 + 7
data = [0] * (10 ** 6 + 1)
data[0] = 1
for i in range(1, 10 ** 6 + 1):
	data[i] = data[i - 1] % mod * i
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for each in a:
		ans += data[each] % mod
	print(ans % mod)


p = 1
d = {}
d[1] = 1
a = 10 ** 9 + 7
for i in range(2, 1000001):
	d[i] = d[i - 1] % a * i
for tc in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	for i in l:
		c += d[i] % a
		c %= a
	print(c)


mod = 10 ** 9 + 7
d = dict()
d[1] = 1
for i in range(2, 1000001):
	d[i] = d[i - 1] * i % mod
t = int(input())
for _ in range(t):
	k = input()
	bag = list((int(i) for i in input().split()))
	sum = 0
	l = map(int, bag)
	for i in bag:
		sum += d[i]
		sum = sum % mod
	print(sum % mod)


a = 10 ** 9 + 7
l = []
l.append(1)
for i in range(2, 1000001):
	l.append(i * l[i - 2] % a)
t = int(input())
while t:
	n = int(input())
	s = list(map(int, input().split()))
	c = 0
	for i in range(n):
		c += l[s[i] - 1]
		c = c % a
	print(c % a)
	t -= 1


d = {}
d[1] = 1
for i in range(2, 1000001):
	d[i] = d[i - 1] * i % 1000000007
n = int(input())
for j in range(n):
	m = int(input())
	arr = list((int(i) for i in input().split()))
	s = 0
	for i in arr:
		s += d[i]
		s %= 1000000007
	print(s % 1000000007)


mod = 10 ** 9 + 7
dp = {}
dp[1] = 1
for i in range(2, 1000000 + 1):
	dp[i] = i * dp[i - 1] % mod
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		ans += dp[arr[i]]
		ans %= mod
	print(ans % mod)


v = 10 ** 9 + 7
f = [1]
for i in range(1, 1000001):
	f.append(i * f[i - 1])
	f[i] = f[i] % v
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	c = 0
	for j in a:
		c = c + f[j] % v
	print(c % v)


from collections import Counter, UserString
mod = lambda n: n % (10 ** 9 + 7)
fc_ = [1]
for i in range(1, 1000001):
	fc_.append(i * fc_[i - 1])
	fc_[i] = mod(fc_[i])

def fact(n):
	return fc_[n]

def printm(n):
	print(mod(n))

def yn(b, caps=False):
	if b:
		returning = 'Yes'
	else:
		returning = 'No'
	if caps:
		return returning.upper()
	return returning

def isPrime(n):
	if n > 1:
		for i in range(2, int(n ** 0.5) + 1):
			if not n % i:
				return False
		else:
			return True
	return True

def decimal(n):
	return int(ans) + int(int(ans) != ans)

class mutableStr(UserString):

	def ins(self, n, s):
		if n < 0:
			self.data = self.data = ''.join(list(self.data)[:n + 1]) + s + ''.join(list(self.data)[n + 1:])
		else:
			self.data = ''.join(list(self.data)[:n]) + s + ''.join(list(self.data)[n:])

	def rem(self, s):
		self.data = self.data.replace(s, '')
alphabetOrd = [97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122]
alphabet = list('abcdefghijklmnopqrstuvwxyz')
r2 = lambda n: range(1, n + 1)
alph = lambda s: s.isalpha()
sl = lambda l: list(set(l))
inf = float('inf')
soi = lambda : sorted(input())
ii = lambda : int(input())
li = lambda : list(map(int, input().split()))
si = lambda : mutableStr(input())
lsi = lambda : list(input())
sepi = lambda : map(int, input().split())
seti = lambda : set(map(int, input().split()))
for t in range(int(input())):
	numOfBalls = ii()
	ballValues = li()
	postNumOfBalls = 0
	for dissociation in ballValues:
		postNumOfBalls += fact(dissociation)
	printm(postNumOfBalls)


t = int(input())
arr = [1] * 1000001
for i in range(2, 1000001):
	arr[i] = arr[i - 1] * i % int(1000000000.0 + 7)
while t:
	t -= 1
	n = input()
	ans = 0
	li = list(map(int, input().split()))
	for i in li:
		ans += arr[i]
		ans = ans % int(1000000000.0 + 7)
	print(ans)


import math
k = pow(10, 9) + 7
fact = [1]
for i in range(2, 1000000 + 2):
	fact.append(i * fact[-1] % k)
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	sum = 0
	for i in range(n):
		sum += fact[l[i] - 1] % k
	print(sum % k)


f = [1]
for i in range(2, 1000001):
	f.append(i * f[-1])
	f[-1] %= 10 ** 9 + 7
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(sum([f[j - 1] for j in a]) % (10 ** 9 + 7))


import sys
test_cases = int(sys.stdin.readline().strip())
M = 1000000007
MAX_A = 1000000
factorial_map = {1: 1}
for i in range(2, MAX_A + 1):
	factorial_map[i] = factorial_map[i - 1] * i % M

def factorial_iter(x):
	return factorial_map[x]

def factorial(x):
	if x in factorial_map:
		return factorial_map[x]
	elif x == 1:
		return 1
	else:
		result = x % M * (factorial(x - 1) % M) % M
		factorial_map[x] = result
		return result

def find_count(array_balls):
	return sum(map(factorial_iter, array_balls)) % M
for i in range(test_cases):
	number_balls = int(sys.stdin.readline().strip())
	array_balls = map(int, sys.stdin.readline().strip().split())
	print(find_count(array_balls))


t = int(input())
m = 1000000000.0 + 7
p = 10000000.0
s = [1] * 1000007
for i in range(2, len(s)):
	s[i] = s[i - 1] * i % m
while t > 0:
	sum = 0
	n = int(input())
	l = list(map(int, input().split()))
	for i in range(len(l)):
		sum += s[l[i]] % m
	print(int(sum % m))
	t = t - 1


import math
fact = [1]
mod = 10 ** 9 + 7
for i in range(1, 10 ** 6 + 1):
	next_fact = fact[-1] * i
	fact.append(next_fact % mod)
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	for x in arr:
		ans += fact[x]
		ans %= mod
	print(ans)


fact = [1]
MOD = 10 ** 9 + 7
for i in range(1, 10 ** 6 + 1):
	next_fact = fact[-1] * i
	fact.append(next_fact % MOD)
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	ans = 0
	for i in range(n):
		ans = (ans + fact[arr[i]]) % MOD
	print(ans)


m = 10 ** 9 + 7
fact = [1]
for i in range(1, 10 ** 6 + 1):
	next = fact[-1] * i
	fact.append(next % m)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = 0
	for k in a:
		d = (d + fact[k]) % m
	print(d)


MOD = 10 ** 9 + 7
fact = [1]
for i in range(1, 10 ** 6 + 1):
	next_fact = fact[-1] * i
	fact.append(next_fact % MOD)
t = int(input())
for i in range(t):
	l = int(input())
	bag = [int(x) for x in input().split()]
	ans = 0
	for i in range(l):
		ans = (ans + fact[bag[i]]) % MOD
	print(ans)


mod = 10 ** 9 + 7
fac = [1, 1]
for x in range(2, 10 ** 6 + 1):
	fac.append(x * fac[x - 1])
	fac[x] %= mod
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for x in a:
		ans += fac[x]
	print(ans % mod)


import math
fact = [1]
for i in range(1, 1000001):
	fact.append(fact[i - 1] * i)
	fact[i] %= 1000000007
for i in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	out = 0
	for i in arr:
		out = out + fact[i]
	out = out % 1000000007
	print(out)


fact = []
fact.append(1)
fact.append(1)
for i in range(2, 1000001):
	fact.append(fact[i - 1] * i)
	fact[i] %= 1000000007
t = int(input())
for _ in range(t):
	n = int(input())
	arr = map(int, input().split(' '))
	res = 0
	for ele in arr:
		res += fact[ele]
	print(res % 1000000007)