There are $N$ colors of beads. You have $b_i$ beads of the $i^{\mbox{th}}$ color. You want to make an ornament by joining all the beads together. You create the ornament by using the following algorithm:

Step #$1$ Arrange all the beads in any order such that beads of the same color are placed together.

Step #$2$ The ornament initially consists of only the first bead from the arrangement.

Step #$3$ For each subsequent bead in order, join it to a bead of the same color in the ornament. If there is no bead of the same color, it can be joined to any bead in the ornament.

All beads are distinct, even if they have the same color. Two ornaments are considered different if two beads are joined by a thread in one configuration, but not in the other.  How many different ornaments can be formed using this algorithm? Return the answer modulo $(10^9+7)$.  

Update/clarification

Think of the bead formation as a tree and not as a straight line. Any number of beads can be connected to a bead.

Example 

$b=[2]$   

There are two beads of color $a$: $a1$ and $a2$.  These can occur as $a1,a2$ or $a2,a1$.  In both cases, the same two beads are joined, so the arrangements are not different.  There is $1$ way to join these beads.   

$b=[2,2]$  

There are two beads of two colors, $a1,a2,b1,b2$.  They can be arranged as $a1,a2$, $a2,a1$, $b1,b2$ and $b2,b1$.  Call these groups $A\mathbf{1}$, $A2$, $\mathbf{B1}$ and $\boldsymbol{B2}$.  The 8 possible arranements of groups are shown below.  

1 A1, B1 = a1, a2, b1, b2
2 A2, B1 = a2, a1, b1, b2
3 A1, B2 = a1, a2, b2, b1
4 A2, B2 = a2, a1, b2, b1
5 B1, A1 = b1, b2, a1, a2
6 B2, A1 = b2, b1, a1, a2 
7 B1, A2 = b1, b2, a2, a1
8 B2, A2 = b2, b1, a2, a1

Note that in line 1, $(a1,a2)$, $(a2,b1)$ and $(b1,b2)$ are the connections.  This also occurs on line 8, so these two lines are not different.  In fact, line 8 is just line 1 reversed, like flipping the string of beads end for end.  Using the same logic, the other similar lines are $(2,6),(3,7),(4,5)$.  There are only 4 different arrangements.  

Function Description   

Complete the beadOrnaments function in the editor below.   

beadOrnaments has the following parameters:   

int b[n]: the number of beads of each color   

Returns   

int: the number of arrangements modulo $(10^9+7)$  

Input Format

The first line contains the number of test cases $\mathbf{T}$. 

Each of the following $\mathbf{T}$ pairs of lines contain: 

- An integer, $n$, the number of elements in array $\boldsymbol{b}$ 

- $n$ space-separated integers that comprise $\boldsymbol{b}$   

Constraints

$1<=T<=20$
$1<=n<=10$
$1<=b[i]<=30$

Sample Input
STDIN       Function
-----       --------
5           T = 5   
2           b[] size n = 2
2 1         b = [2, 1]
2           n = 2
2 2         b = [2, 2]
1           n = 1
4           b = [4]
2           n = 2
3 1         b = [3, 1]
5           n = 5
1 1 1 1 1   b = [1, 1, 1, 1, 1]

Sample Output
2
4
16
9
125

Explanation

Testcase 1:

Let us label the beads A1,A2 and B1. Initially, they can be arranged in $4$ ways - "A1,A2,B1", "A2,A1,B1", "B1,A1,A2", and "B1,A2,A1". 

For each of the first two arrangements, an ornament can be formed in $2$ ways (A1-A2-B1 or B1-A1-A2 from the first one and A2-A1-B1 or B1-A2-A1 from the second one). 

For each of the last two arrangements, an ornament can be formed in $1$ way. 

However, of the total $\boldsymbol{6}$ possible ornaments, there are only $2$ unique ones : A1 - A2 - B1, and A2 - A1 - B1.

Testcase 2:

The possible unique ornaments are A1 - A2 - B1 - B2, A1 - A2 - B2 - B1, A2 - A1 - B1 - B2, and A2 - A1 - B2 - B1.

Testcase 3:

For the third test-case, it might be easier to see there are only $2$ types of graphs on $4$ vertices: the path or the star. It's not hard to see that there are $12$ paths and $4$ stars (explanation courtesy: zlangley)

Testcase 5:

For the fifth test-case, a lot of people claimed that the total number of possible ways is $5!/2=60$. But that is wrong. The correct answer is $125$. Here's the hint: Once again, you've to think of it as a tree. 

So one possible arrangement can be:

A is a root node and has two edges (A-B and A-C). Now, think of B as a sub-root node with two edges (B-D and B-E). Similarly, you can figure out the other possible bead arrangements. This will lead you to the correct answer.

Difficulty: HARD
Tags: Graph algorithms

Starter code:

Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	ans = 1
	s = 0
	a = input()
	b = [int(a) for a in a.split(' ')]
	for j in b:
		ans = ans * j ** (j - 1)
		s = s + j
	ans = ans * s ** (n - 2)
	ans = ans % 1000000007
	print(int(ans))


def solve(vals):
	n = len(vals)
	if n == 1:
		return pow(vals[0], vals[0] - 2, 1000000007)
	s = sum(vals)
	p = 1
	for i in vals:
		p = p * pow(i, i - 1, 1000000007) % 1000000007
	return p * pow(s, n - 2, 1000000007) % 1000000007
n = int(input())
for i in range(n):
	x = int(input())
	vals = [int(i) for i in input().split(' ')]
	print(solve(sorted(vals)))


import sys

def product(numbers):
	result = 1
	for number in numbers:
		result *= number
	return result

def cayley(n):
	assert n > 0
	if n == 1:
		return 1
	else:
		return n ** (n - 2)
T = int(sys.stdin.readline())
for case in range(T):
	N = int(sys.stdin.readline())
	beads = [int(X) for X in sys.stdin.readline().split()]
	cayleys = [cayley(bead) for bead in beads]
	if N == 1:
		answer = cayleys[0]
		print(answer % 1000000007)
	else:
		answer = product(beads) * sum(beads) ** (N - 2)
		answer *= product(cayleys)
		print(answer % 1000000007)


T = int(input())
for a in range(T):
	N = int(input())
	b = [int(next) for next in input().split(' ')]
	ans = 1
	for x in b:
		ans *= x ** (x - 1)
	ans *= sum(b) ** (N - 2)
	print(int(ans) % 1000000007)


import math
import operator
import functools
import itertools
modval = 1000000007
N = int(input())
for i in range(N):
	color_count = int(input())
	bead_counts = [int(x) for x in input().split()]
	bc_pieces = [int(bc ** (bc - 2)) for bc in bead_counts]
	bc_piece_ways = [int(bead_counts[i] * bc_pieces[i]) for i in range(color_count)]
	bcpw_prod = int(functools.reduce(operator.mul, bc_piece_ways))
	s_bc = sum(bead_counts)
	s_bc_n = s_bc ** (color_count - 2)
	print(int(bcpw_prod * s_bc_n) % modval)


T = int(input())
for a in range(T):
	N = int(input())
	b = [int(next) for next in input().split(' ')]
	ans = 1
	for x in b:
		ans *= x ** (x - 1)
	ans *= sum(b) ** (N - 2)
	print(int(ans) % 1000000007)


from operator import mul
from functools import reduce
LP = 1000000007
test_cases = int(input())
for i in range(test_cases):
	no_of_beads = int(input())
	beads = [int(x) for x in input().split()]
	tree_comps = [x ** (x - 2) % LP if x > 2 else 1 for x in beads]
	k = len(beads)
	n = sum(beads)
	pi_s = reduce(mul, beads, 1) % LP
	pi_c = reduce(mul, tree_comps, 1) % LP
	n_k2 = n ** (k - 2) % LP if k > 1 else 1
	if k > 1:
		print(pi_s * pi_c * n_k2 % LP)
	else:
		print(pi_c % LP)


def rmain():
	input()
	lst = [int(x) for x in input().split(' ')]
	n = len(lst)
	answer = 1
	for x in lst:
		answer *= x ** (x - 1)
	answer *= sum(lst) ** (n - 2)
	print(int(answer) % 1000000007)
ncase = int(input())
for i in range(ncase):
	rmain()


import math
t = int(input())
for i in range(t):
	ans = 1
	sumb = 0
	n = int(input())
	str1 = input()
	for b in str1.split():
		b = int(b)
		sumb += b
		ans *= b ** (b - 1)
		ans = ans % 1000000007
	ans *= sumb ** (n - 2)
	ans = ans % 1000000007
	print(int(ans))


__doc__ = "\nreview: http://blog.hackerrank.com/bead-ornaments-challenge/\nConsider each color will build a tree which follow:\nhttps://en.wikipedia.org/wiki/Cayley%27s_formula\n(Cayley's Formula) T(n) = n ^ (n-2)\nThen the answer is:\nhttps://github.com/adr2370/HackerRankBackToSchool/blob/master/Beadornaments.py\n\n"

def solution(N, B, m=1000000007):
	ans = 1
	for x in B:
		ans *= x ** (x - 1)
	ans *= sum(b) ** (N - 2)
	return int(ans) % m
T = int(input())
todo = []
for i in range(T):
	N = int(input())
	Bline = input()
	todo.append((N, [int(i) for i in Bline.split()]))
for (n, b) in todo:
	print(solution(n, b))


T = int(input())
for i in range(T):
	N = int(input())
	b = [int(x) for x in input().strip().split()]
	result = 1
	for i in b:
		result *= i ** (i - 1)
	result *= sum(b) ** (N - 2)
	print(round(result % 1000000007))


import math
t = int(input())
for i in range(t):
	ans = 1
	sumb = 0
	n = int(input())
	str1 = input()
	for b in str1.split():
		b = int(b)
		sumb += b
		ans *= b ** (b - 1)
		ans = ans % 1000000007
	ans *= sumb ** (n - 2)
	ans = ans % 1000000007
	print(int(ans))


import math
t = int(input())
for i in range(t):
	ans = 1
	sumb = 0
	n = int(input())
	str1 = str(input())
	for b in str1.split():
		b = int(b)
		sumb += b
		ans *= b ** (b - 1)
		ans = ans % 1000000007
	ans *= sumb ** (n - 2)
	ans = ans % 1000000007
	print(int(ans))


from collections import Counter
from itertools import chain, combinations
MOD = int(1000000000.0) + 7

def powerset(n):
	r = range(n)
	return chain.from_iterable((combinations(r, l) for l in range(1, n + 1)))

def partitions(n, index):
	if index == 0:
		yield [n[:1]]
		return
	for p in partitions(n, index - 1):
		yield (p + [[n[index]]])
		for x in p:
			x.append(n[index])
			yield p
			del x[-1]
for _ in range(int(input())):
	n = int(input())
	counts = {}
	ways = Counter()
	for (i, x) in enumerate(input().split()):
		component_count = int(x)
		counts[tuple([i])] = component_count
		ways[tuple([i])] = int(component_count ** (component_count - 2))
		for s in powerset(i):
			key = tuple(s) + (i,)
			counts[key] = component_count + counts[tuple(s)]
			for p in partitions(list(s), len(s) - 1):
				y = 1
				for x in p:
					y = y * ways[tuple(x)] * counts[tuple(x)] * component_count
				ways[key] += y * ways[tuple([i])]
	print(ways[tuple(range(n))] % MOD)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	ans = sum(l) ** (n - 2)
	for i in l:
		ans *= i ** (i - 1)
	print(int(ans % 1000000007))


T = int(input())
for a in range(T):
	N = input()
	N = int(N)
	b = [int(next) for next in input().split()]
	ans = 1
	for x in b:
		ans *= x ** (x - 1)
	ans *= sum(b) ** (N - 2)
	print(int(ans) % 1000000007)


t = int(input())
for i in range(t):
	n = int(input())
	ans = 1
	s = 0
	a = input()
	b = [int(a) for a in a.split(' ')]
	for j in b:
		ans = ans * j ** (j - 1)
		s = s + j
	ans = ans * s ** (n - 2)
	ans = ans % 1000000007
	print(int(ans))


import math
t = int(input())
for i in range(t):
	ans = 1
	sum_n = 0
	n = int(input())
	str1 = input()
	for b in str1.split():
		b = int(b)
		sum_n += b
		ans = ans * b ** (b - 1)
		ans = ans % 1000000007
	ans = ans * sum_n ** (n - 2)
	ans = ans % 1000000007
	print(int(ans))


from functools import reduce
M = 10 ** 9 + 7

def powM(b, e):
	return (powM(b, e >> 1) ** 2 * b % M if e & 1 else powM(b, e >> 1) ** 2 % M) if e > 1 else b if e == 1 else 1 if e == 0 else powM(powM(b, M - 2), -e)
C = [powM(x, x - 1) for x in range(31)]
for _ in range(int(input())):
	(n, data) = (int(input()), [int(x) for x in input().split(' ')])
	print(reduce(lambda s, c: s * C[c] % M, data, 1) * powM(sum(data), n - 2) % M)


import math
t = int(input())
for i in range(t):
	ans = 1
	sumb = 0
	n = int(input())
	str1 = input()
	for b in str1.split():
		b = int(b)
		sumb += b
		ans *= b ** (b - 1)
		ans = ans % 1000000007
	ans *= sumb ** (n - 2)
	ans = ans % 1000000007
	print(int(ans))


t = int(input())
for i in range(t):
	comb = 1
	beads = 0
	n = int(input())
	s = input()
	for i in s.split():
		i = int(i)
		beads += i
		comb *= i ** (i - 1)
		comb = comb % 1000000007
	comb *= beads ** (n - 2)
	comb = comb % 1000000007
	print(int(comb))


import math
t = int(input())
for i in range(t):
	ans = 1
	sumb = 0
	n = int(input())
	str1 = input()
	for b in str1.split():
		b = int(b)
		sumb += b
		ans *= b ** (b - 1)
		ans = ans % 1000000007
	ans *= sumb ** (n - 2)
	ans = ans % 1000000007
	print(int(ans))


import math
t = int(input())
for i in range(t):
	ans = 1
	sumb = 0
	n = int(input())
	str1 = input()
	for b in str1.split():
		b = int(b)
		sumb += b
		ans *= b ** (b - 1)
		ans = ans % 1000000007
	ans *= sumb ** (n - 2)
	ans = ans % 1000000007
	ans = int(ans)
	print(ans)


import math
t = int(input())
for i in range(t):
	ans = 1
	sumb = 0
	n = int(input())
	str1 = input()
	for b in str1.split():
		b = int(b)
		sumb += b
		ans *= b ** (b - 1)
		ans = ans % 1000000007
	ans *= sumb ** (n - 2)
	ans = ans % 1000000007
	print(int(ans))


import math
t = int(input())
for i in range(t):
	ans = 1
	sumb = 0
	n = int(input())
	str1 = input()
	for b in str1.split():
		b = int(b)
		sumb += b
		ans *= b ** (b - 1)
		ans = ans % 1000000007
	ans *= sumb ** (n - 2)
	ans = ans % 1000000007
	print(int(ans))


import os
import sys
import math
t = int(input())
for i in range(t):
	ans = 1
	sumb = 0
	n = int(input())
	str1 = input()
	for b in str1.split():
		b = int(b)
		sumb += b
		ans *= b ** (b - 1)
		ans = ans % 1000000007
	ans *= sumb ** (n - 2)
	ans = ans % 1000000007
	ans = int(ans)
	print(ans)


import math
t = int(input())
for i in range(t):
	ans = 1
	sumb = 0
	n = int(input())
	str1 = input()
	for b in str1.split():
		b = int(b)
		sumb += b
		ans *= b ** (b - 1)
		ans = ans % 1000000007
	ans *= sumb ** (n - 2)
	ans = ans % 1000000007
	print(int(ans))


import math
t = int(input())
for i in range(t):
	ans = 1
	sumb = 0
	n = int(input())
	str1 = input()
	for b in str1.split():
		b = int(b)
		sumb += b
		ans *= b ** (b - 1)
		ans = ans % 1000000007
	ans *= sumb ** (n - 2)
	ans = ans % 1000000007
	print(int(ans))


import math
t = int(input())
for i in range(t):
	ans = 1
	sumb = 0
	n = int(input())
	str1 = input()
	for b in str1.split():
		b = int(b)
		sumb += b
		ans *= b ** (b - 1)
		ans = ans % 1000000007
	ans *= sumb ** (n - 2)
	ans = ans % 1000000007
	print(int(ans))


t = int(input())
for i in range(t):
	n = int(input())
	ans = 1
	s = 0
	a = input()
	b = [int(a) for a in a.split(' ')]
	for j in b:
		ans = ans * j ** (j - 1)
		s = s + j
	ans = ans * s ** (n - 2)
	ans = ans % 1000000007
	print(int(ans))


import math
t = int(input())
for i in range(t):
	ans = 1
	sumb = 0
	n = int(input())
	str1 = input()
	for b in str1.split():
		b = int(b)
		sumb += b
		ans *= b ** (b - 1)
		ans = ans % 1000000007
	ans *= sumb ** (n - 2)
	ans = int(ans % 1000000007)
	print(ans)


__author__ = 'camilo ariza'
__email__ = 'camilo.ariza@protonmail.com'
__created__ = 'Sat 17 Oct 2020 15:04:12 -0300'
__modified__ = 'Sat 17 Oct 2020 15:09:28 -0300'
from operator import mul
from functools import reduce

def bead_ornaments(b, n):
	return int(reduce(mul, map(lambda x: x ** (x - 1), b)) * sum(b) ** (n - 2) % (7 + 10 ** 9))
for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().strip().split()))
	print(bead_ornaments(b, n))


import os
import sys
t = int(input())
for i in range(t):
	n = int(input())
	ans = 1
	s = 0
	a = input()
	b = [int(a) for a in a.split(' ')]
	for j in b:
		ans = ans * j ** (j - 1)
		s = s + j
	ans = ans * s ** (n - 2)
	ans = ans % 1000000007
	print(int(ans))


from operator import mul
from functools import reduce

def beadOrnaments(b):
	return int(reduce(mul, map(lambda x: x ** (x - 1), b), 1) * sum(b) ** (len(b) - 2) % (7 + 10 ** 9))
t = int(input())
for i in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	print(beadOrnaments(b))