Given N distinct digits in an array A (from 1 to 9), Your task is to complete the function getSum which finds sum of all n digit numbers that can be formed using these digits. 
Note: Since the output can be large take modulo 1000000007
Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains an integer N . In the next line are N space separated digits.
Output:
For each test case in a new line output will be the sum of all n digit numbers that can be formed using these digits.
Constraints:
1<=T<=100
1<=N<=9
Example(To be used only for expected output):
Input:
2
3
1 2 3
2
1 2
Output:
1332
33
Explanation:
For first test case
the numbers formed will be 123 , 132 , 312 , 213, 231 , 321
sum = 123 + 132 + 312 + 213 + 231 + 321 = 1332
For second test case
the numbers formed will be 12, 21
sum = 12 + 21 = 33

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Number theory

Data structures

Starter code: #Function should return an integer
#You may use python modules
MOD = 10**9+7
def getSum(n, arr):
    #Code here


Solutions:
from itertools import permutations
MOD = 10 ** 9 + 7

def getSum(n, arr):
	for i in range(0, n):
		arr[i] = str(arr[i])
	a = 0
	for c in permutations(arr, n):
		k = int(''.join(c))
		a = a + k
	return a % MOD


from itertools import permutations
MOD = 10 ** 9 + 7

def getSum(n, arr):
	arr = [str(i) for i in arr]
	perm = permutations(arr)
	s = 0
	for a in perm:
		curr = int(''.join(a))
		s += curr
	return s % MOD


MOD = 10 ** 9 + 7
from itertools import permutations

def getSum(n, arr):
	per = permutations(arr)
	ans = 0
	for i in per:
		ans = (ans + int(''.join((str(x) for x in i))) % MOD) % MOD
	return ans


from itertools import permutations
MOD = 10 ** 9 + 7

def getSum(n, arr):
	num = ''
	for i in arr:
		num += ''.join(str(i))
	l = list(permutations(num, len(arr)))
	s = 0
	for i in l:
		s += int(''.join(i))
	return s % MOD


MOD = 10 ** 9 + 7

def factorial(n):
	f = 1
	if n == 0 or n == 1:
		return 1
	for i in range(2, n + 1):
		f = f * i
	return f

def getSum(n, arr):
	fact = factorial(n)
	digitsum = 0
	for i in range(n):
		digitsum += arr[i]
	digitsum *= fact // n
	res = 0
	i = 1
	k = 1
	while i <= n:
		res += k * digitsum
		k = k * 10
		i += 1
	return res % MOD


MOD = 10 ** 9 + 7

def getSum(n, a):
	ans = 0
	fact = 1
	for i in range(1, n):
		fact = fact * i
	for i in range(n):
		x = 0
		for j in range(n):
			x = x * 10 + a[i]
		ans += fact * x
	return ans % MOD


from math import factorial as f
MOD = 10 ** 9 + 7

def getSum(n, arr):
	a = f(n - 1)
	s = sum(arr)
	ans = ''
	b = s * a
	carry = 0
	for i in range(n):
		if i == n - 1:
			ans = str(b + carry) + ans
		w = b + carry
		q = str(w)
		ans = q[-1] + ans
		if q[0:-1] != '':
			carry = int(q[0:-1])
	return int(ans[1:]) % MOD


MOD = 10 ** 9 + 7
from itertools import permutations

def getSum(n, arr):
	arr = list(map(str, arr))
	k = list(permutations(arr, n))
	ss = 0
	for i in k:
		sk = ''.join(i)
		ss = (ss + int(sk)) % MOD
	return ss


MOD = 10 ** 9 + 7
from math import factorial

def getSum(n, arr):
	count = factorial(n - 1)
	s = sum(arr) * count
	val = 0
	for x in range(n):
		val = (val + s) % MOD
		s *= 10
	return val


def perm(n, arr):
	stack = []
	vis = set()
	helper(n, '', vis, stack, arr)
	return sum(stack) % (10 ** 9 + 7)

def helper(n, text, vis, stack, arr):
	if len(text) == n:
		tmp = ''
		for let in text:
			a = int(let)
			tmp += str(arr[a - 1])
		stack.append(int(tmp))
	for i in range(1, n + 1):
		if i not in vis:
			vis.add(i)
			helper(n, text + str(i), vis, stack, arr)
			vis.remove(i)

def getSum(n, arr):
	return perm(n, arr)


MOD = 10 ** 9 + 7

def getSum(n, arr):

	def call(n, arr, s, f, l):
		if len(s) == n:
			l.append(int(s))
			return
		for i in range(n):
			if f[i] == 0:
				f[i] = 1
				s += arr[i]
				call(n, arr, s, f, l)
				f[i] = 0
				s = s[:-1]
	f = [0] * n
	s = ''
	l = []
	a = []
	for i in arr:
		a.append(str(i))
	call(n, a, s, f, l)
	return sum(l) % MOD


import math
MOD = 10 ** 9 + 7

def getSum(n, arr):
	sum_arr = 0
	for i in arr:
		sum_arr = sum_arr + i
	time = int(math.factorial(n) / n)
	s = sum_arr * time
	res = 0
	for i in range(n):
		res = res + s * 10 ** i
	return res % MOD


from math import factorial
MOD = 10 ** 9 + 7

def getSum(n, arr):
	return sum(arr) * int('1' * n) * factorial(n - 1) % MOD


MOD = 10 ** 9 + 7

def fac(n):
	if n == 0 or n == 1:
		return 1
	else:
		fac = 1
		for i in range(2, n + 1):
			fac = fac * i
		return fac

def getSum(n, arr):
	fact = fac(n)
	occ = fact / n
	sum = 0
	for i in range(len(arr)):
		sum = sum + arr[i]
	digitsum = sum * occ
	res = 0
	i = 1
	k = 1
	while i <= n:
		res += k * digitsum
		k = k * 10
		i += 1
	return int(res) % 1000000007


MOD = 10 ** 9 + 7

def fact(n):
	if n < 2:
		return 1
	else:
		return n * fact(n - 1)

def getSum(n, arr):
	val1 = int('1' * n)
	summ = 0
	for i in range(n):
		summ += arr[i] * fact(n - 1) / arr.count(arr[i]) * val1
	return int(summ % MOD)


MOD = 10 ** 9 + 7
from itertools import permutations

def getSum(n, arr):
	k = list(permutations(arr))
	ans = 0
	for i in k:
		s = ''
		for j in i:
			s += str(j)
		ans = (ans + int(s)) % MOD
	return ans


import math
MOD = 10 ** 9 + 7

def getSum(n, arr):
	fact = math.factorial(n)
	digitsum = 0
	for i in range(n):
		digitsum += arr[i]
	digitsum *= fact // n
	res = 0
	i = 1
	k = 1
	while i <= n:
		res += k * digitsum
		k = k * 10
		i += 1
	return res % MOD


MOD = 10 ** 9 + 7

def getSum(n, arr):
	mult = 1
	for i in range(1, n):
		mult = mult * i
	sum_digits = sum(arr)
	final_answer = ''
	carryover = 0
	for i in range(n - 1):
		digit = (sum_digits * mult + carryover) % 10
		carryover = (sum_digits * mult + carryover) // 10
		final_answer = str(digit) + final_answer
	final_answer = str(sum_digits * mult + carryover) + final_answer
	return int(final_answer) % MOD


MOD = 10 ** 9 + 7
from itertools import permutations

def getSum(n, arr):
	for i in range(n):
		arr[i] = str(arr[i])
	l = permutations(arr)
	s = 0
	for i in l:
		s1 = ''.join(i)
		s = s + int(s1) % MOD
	return s % MOD


MOD = 10 ** 9 + 7

def getSum(n, arr):
	from itertools import permutations
	b = ''
	for i in arr:
		b += str(i)
	l = []
	for i in permutations(b):
		a = ''.join(i)
		l.append(int(a))
	c = sum(l) % MOD
	return c


from itertools import permutations
MOD = 10 ** 9 + 7

def getSum(n, arr):
	s = ''.join(map(str, arr))
	p = list(permutations(s))
	ans = 0
	for perms in p:
		val = ''.join(map(str, perms))
		res = int(val)
		ans += res
	return ans % 1000000007


from math import factorial
MOD = 10 ** 9 + 7

def getSum(n, arr):
	perms_per_fix = factorial(n - 1)
	sum = 0
	for number in arr:
		for tens_power in range(0, n):
			from_one_perm = number * 10 ** tens_power
			sum += from_one_perm * perms_per_fix
	return sum % MOD


MOD = 10 ** 9 + 7

def factorial(n):
	ans = 1
	if n == 0 or n == 1:
		return 1
	else:
		ans = n * factorial(n - 1)
		return ans

def getSum(n, arr):
	ans = 0
	sum_ = sum(arr)
	fact = factorial(n)
	sum_ *= fact // n
	n -= 1
	while n >= 0:
		ans += sum_ * 10 ** n
		n -= 1
	return ans % MOD


MOD = 10 ** 9 + 7

def factorial(n):
	ans = 1
	if n == 0 or n == 1:
		return 1
	else:
		for i in range(2, n + 1):
			ans = ans * i
		return ans

def getSum(n, arr):
	ans = 0
	sum_ = sum(arr)
	fact = factorial(n)
	sum_ *= fact // n
	n -= 1
	while n >= 0:
		ans += sum_ * 10 ** n
		n -= 1
	return ans % MOD


MOD = 10 ** 9 + 7

def factorial(n):
	result = 1
	while n > 0:
		result *= n
		n -= 1
	return result

def getSum(n, arr):
	times = factorial(n - 1)
	result = 0
	for x in arr:
		for po in range(0, n):
			result += x * 10 ** po * times
	return result % MOD


MOD = 10 ** 9 + 7
from itertools import permutations

def getSum(n, arr):
	s = list(map(str, arr))
	v = ''.join(s)
	t = list(permutations(v))
	q = []
	s = 0
	for j in range(len(t)):
		r = ''.join(t[j])
		s = s + int(r)
	return s % MOD


MOD = 10 ** 9 + 7

def per(c, arr, l, n):
	if c == n - 1:
		e = ''.join(arr)
		l[0] += int(e)
		l[0] = l[0] % 1000000007
		return
	for i in range(c, n):
		(arr[i], arr[c]) = (arr[c], arr[i])
		per(c + 1, arr, l, n)
		(arr[i], arr[c]) = (arr[c], arr[i])

def getSum(n, arr):
	l = [0]
	per(0, arr, l, n)
	return l[0]


from itertools import permutations
MOD = 10 ** 9 + 7

def getSum(n, arr):
	arr = list(map(str, arr))
	s = ''
	su = 0
	for val in permutations(arr, n):
		s = ''.join(val)
		su += int(s)
	return su % MOD
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		print(getSum(n, arr))


from itertools import permutations as p
MOD = 10 ** 9 + 7

def getSum(n, arr):
	a = list(p(arr))
	b = []
	for j in a:
		c = ''.join((str(k) for k in j))
		b.append(int(c))
	r = sum(b) % MOD
	return r


MOD = 10 ** 9 + 7

def factorial(n):
	dp = [1] * (n + 1)
	for i in range(2, n + 1):
		dp[i] = i * dp[i - 1]
	return dp

def sumdigits(n):
	result = 0
	while n:
		result += n % 10
		n = n // 10
	return result

def getSum(n, arr):
	fact = factorial(n)
	digitsum = sum(arr)
	F = fact[n] // n * digitsum
	R = 0
	i = 0
	while i < n:
		R += 10 ** i * F
		i += 1
	return R % MOD


MOD = 10 ** 9 + 7

def getSum(n, arr):
	count = 0
	for i in range(n):
		count += arr[i]
	fact = 1
	for i in range(1, n + 1):
		fact *= i
	count = count * fact // n
	k = 1
	res = 0
	i = 1
	while i <= n:
		res += k * count
		k *= 10
		i += 1
	return res % MOD


MOD = 10 ** 9 + 7
permutations = []

def get_sum(arr, number):
	if not arr:
		permutations.append(number)
		return
	for iter in range(len(arr)):
		left_element = arr.copy()
		number_subset = number * 10 + left_element[iter]
		del left_element[iter]
		get_sum(left_element, number_subset)

def getSum(size, arr):
	global permutations
	get_sum(arr, 0)
	sum_permutations = 0
	for iter in permutations:
		sum_permutations += iter
	permutations = []
	return sum_permutations % MOD


def fact(n):
	f = 1
	if n == 0 or n == 1:
		return 1
	for i in range(2, n + 1):
		f *= i
	return f

def getSum(n, arr):
	f = fact(n)
	tot = sum(arr)
	tot *= f // n
	(res, i, k) = (0, 1, 1)
	while i <= n:
		res += k * tot
		k = k * 10
		i += 1
	return res % 1000000007


from itertools import permutations
MOD = 10 ** 9 + 7

def getSum(n, arr):
	s = 0
	for i in permutations(arr, n):
		num = 0
		for j in i:
			num = num * 10 + j
		s += num
	return s % MOD


import math
MOD = 10 ** 9 + 7

def getSum(n, arr):
	x = 0
	s = 1
	while x < len(arr) - 1:
		x += 1
		s += 10 ** x
	summ = sum(arr)
	return math.factorial(len(arr) - 1) * s * summ % 1000000007


MOD = 10 ** 9 + 7

def getSum(n, arr):
	import itertools
	t = [z for z in itertools.permutations(arr)]
	s = 0
	for i in t:
		m = ''
		for j in i:
			m += str(j)
		s += int(m)
	return s % 1000000007


from math import pow
MOD = 10 ** 9 + 7

def fact(n):
	f = 1
	for i in range(2, n + 1):
		f *= i
	return f

def getSum(n, arr):
	sum_value = 0
	for i in range(0, n):
		sum_value += arr[i]
	f = fact(n)
	actual_sum_value = sum_value * (f // n)
	result = 0
	power = 0
	temp_sum = actual_sum_value
	while n != 1:
		result = temp_sum % 10 * pow(10, power) + result
		temp_sum = temp_sum // 10 + actual_sum_value
		power += 1
		n -= 1
	result = (temp_sum // 10 + actual_sum_value) * pow(10, power) + result
	return int(result % MOD)


MOD = 10 ** 9 + 7
from itertools import permutations

def getSum(n, arr):
	arr = ''.join(list(map(str, arr)))
	numbers = [''.join(p) for p in permutations(arr)]
	numbers = list(map(int, numbers))
	return sum(numbers) % MOD