Sevenkplus has a rooted tree with $N$ vertices. The vertices are labeled from $1$ to $N$. $1$ is the root of the tree. Each vertex $v$ has a weight $W_v$. 

He forms a $N\times N$ matrix ${M}$ from the tree. ${M}$ is defined by 

$M(x,y)=W_{lca(x,y)}$ 

where $lca(x,y)$ is the lowest common ancestor of vertex ${x}$ and vertex $y$. 

He wants to calculate the determinant of ${M}$.  

Input Format 

First line contains the number of vertices, $N$. 

Second line contains $N$ numbers, $W_1\:W_2\:\cdots\:W_N$ separated by a space. 

This is followed by $N-1$ lines. Each line contains two numbers ${x}$, $y$, denoting that there is an edge between ${x}$  and $y$.  

Output Format 

Output one line, the determinant of ${M}$ modulo $(10^9+7)$.

Constraints 

$1\leq N\leq10^5$ 

$\forall i,0\leq W_i\leq10^9$. 

Sample Input

3
1 2 3
1 2
1 3

Sample Output

2

Explanation

$M=\begin{bmatrix}1&1&1\\ 1&2&1\\ 1&1&3\end{bmatrix}$

Then, $|M|=1\times\begin{bmatrix}2&1\\ 1&3\end{bmatrix}-1\times\begin{bmatrix}1&1\\ 1&3\end{bmatrix}+1\times\begin{bmatrix}1&2\\ 1&1\end{bmatrix}$. 

Hence $|M|=(1\times5)-(1\times2)+(1\times-1)=2$

Timelimits 

Timelimits for this challenge is given here

Source: hackerrank | Difficulty: MEDIUM
Tags: Number theory


Solutions:
import collections, sys
MOD = 1000000007

def dfs_compute(tree, weights, root):
	visited = set()
	stack = [(-1, root)]
	product = 1
	while stack:
		(parent, node) = stack.pop()
		if node not in visited:
			visited.add(node)
			product *= weights[node - 1] - (weights[parent - 1] if parent > -1 else 0)
			product %= MOD
			for child in tree[node] - visited:
				stack.append((node, child))
	return product
N = int(sys.stdin.readline())
W = list(map(int, sys.stdin.readline().split()))
tree = collections.defaultdict(set)
for _ in range(N - 1):
	(x, y) = list(map(int, sys.stdin.readline().split()))
	tree[x].add(y)
	tree[y].add(x)
print(dfs_compute(tree, W, 1))


import collections, sys
MOD = 1000000007

def dfs_compute(tree, weights, root):
	visited = set()
	stack = [(-1, root)]
	product = 1
	while stack:
		(parent, node) = stack.pop()
		if node not in visited:
			visited.add(node)
			product *= weights[node - 1] - (weights[parent - 1] if parent > -1 else 0)
			product %= MOD
			for child in tree[node] - visited:
				stack.append((node, child))
	return product
N = int(sys.stdin.readline())
W = list(map(int, sys.stdin.readline().split()))
tree = collections.defaultdict(set)
for _ in range(N - 1):
	(x, y) = list(map(int, sys.stdin.readline().split()))
	tree[x].add(y)
	tree[y].add(x)
print(dfs_compute(tree, W, 1))


import collections, sys
MOD = 1000000007

def dfs_compute(tree, weights, root):
	visited = set()
	stack = [(-1, root)]
	product = 1
	while stack:
		(parent, node) = stack.pop()
		if node not in visited:
			visited.add(node)
			product *= weights[node - 1] - (weights[parent - 1] if parent > -1 else 0)
			product %= MOD
			for child in tree[node] - visited:
				stack.append((node, child))
	return product
N = int(sys.stdin.readline())
W = list(map(int, sys.stdin.readline().split()))
tree = collections.defaultdict(set)
for _ in range(N - 1):
	(x, y) = list(map(int, sys.stdin.readline().split()))
	tree[x].add(y)
	tree[y].add(x)
print(dfs_compute(tree, W, 1))


import collections, sys
MOD = 1000000007

def dfs_compute(tree, weights, root):
	visited = set()
	stack = [(-1, root)]
	product = 1
	while stack:
		(parent, node) = stack.pop()
		if node not in visited:
			visited.add(node)
			product *= weights[node - 1] - (weights[parent - 1] if parent > -1 else 0)
			product %= MOD
			for child in tree[node] - visited:
				stack.append((node, child))
	return product
N = int(sys.stdin.readline())
W = list(map(int, sys.stdin.readline().split()))
tree = collections.defaultdict(set)
for _ in range(N - 1):
	(x, y) = list(map(int, sys.stdin.readline().split()))
	tree[x].add(y)
	tree[y].add(x)
print(dfs_compute(tree, W, 1))


import collections, sys
MOD = 1000000007

def dfs_compute(tree, weights, root):
	visited = set()
	stack = [(-1, root)]
	product = 1
	while stack:
		(parent, node) = stack.pop()
		if node not in visited:
			visited.add(node)
			product *= weights[node - 1] - (weights[parent - 1] if parent > -1 else 0)
			product %= MOD
			for child in tree[node] - visited:
				stack.append((node, child))
	return product
N = int(sys.stdin.readline())
W = list(map(int, sys.stdin.readline().split()))
tree = collections.defaultdict(set)
for _ in range(N - 1):
	(x, y) = list(map(int, sys.stdin.readline().split()))
	tree[x].add(y)
	tree[y].add(x)
print(dfs_compute(tree, W, 1))


n = int(input())
ws = [0] + [int(x) for x in input().split()]
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(a, b) = [int(x) for x in input().split()]
	graph[a].append(b)
	graph[b].append(a)
depth = {1: 0}
visit = [1]
parent = [0 for _ in range(n + 1)]
while visit:
	node = visit.pop(0)
	for child in graph[node]:
		if child not in depth:
			parent[child] = node
			depth[child] = depth[node] + 1
			visit.append(child)
mod = 10 ** 9 + 7
res = 1
for i in range(1, n + 1):
	res = res * (ws[i] - ws[parent[i]]) % mod
print(res)


n = int(input())
w = list(map(int, input().split()))
L = [[w[i], []] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	L[a - 1][1].append(b - 1)
	L[b - 1][1].append(a - 1)
D = 1
l = [(0, 0)]
while l:
	(i, w) = l.pop()
	D = D * (L[i][0] - w) % (10 ** 9 + 7)
	l += [(t, L[i][0]) for t in L[i][1]]
	for t in L[i][1]:
		L[t][1].remove(i)
print(D)


from collections import deque
stack = deque()
N = int(input())
wts = list(map(int, input().split()))
tree = [[] for i in range(N + 1)]
mod = pow(10, 9) + 7
if N == 1:
	print(wts[0] % mod)
else:
	for i in range(N - 1):
		(x, y) = list(map(int, input().split()))
		tree[x].append(y)
		tree[y].append(x)
	stack.append(1)
	while len(stack) > 0:
		num = stack.pop()
		children = tree[num]
		for child in children:
			stack.append(child)
			tree[child].remove(num)
	d = dict()
	for i in range(len(wts)):
		d[i + 1] = wts[i]
	popped_once = set()
	stack = deque()
	dets = dict()
	popped_once.add(1)
	children = tree[1]
	stack.append(1)
	for child in children:
		stack.append(child)
	while len(stack) > 0:
		item = stack.pop()
		children = tree[item]
		if len(children) == 0:
			dets[item] = 1
		elif item in popped_once:
			prod = 1
			for child in children:
				prod = prod * (d[item] - d[child]) % mod
				prod = prod * dets[child] % mod
			prod = prod * (-1) ** (len(children) % 2)
			dets[item] = prod
		else:
			stack.append(item)
			popped_once.add(item)
			for child in children:
				stack.append(child)
	print(dets[1] * d[1] % mod)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


mod = 10 ** 9 + 7
n = int(input())
w = list(map(int, str(input()).strip().split(' ')))
w.append(0)
adj = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = list(map(int, str(input()).strip().split(' ')))
	a -= 1
	b -= 1
	adj[a].append(b)
	adj[b].append(a)
stack = [(0, n)]
det = 1
while stack:
	(i, p) = stack.pop()
	det *= w[i] - w[p]
	det %= mod
	for j in adj[i]:
		if j == p:
			continue
		stack.append((j, i))
print(det)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for i in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


n = int(input())
w = list(map(int, input().split()))
L = [[w[i], []] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	L[a - 1][1].append(b - 1)
	L[b - 1][1].append(a - 1)
D = 1
l = [(0, 0)]
while l:
	(i, w) = l.pop()
	D = D * (L[i][0] - w) % (10 ** 9 + 7)
	l += [(t, L[i][0]) for t in L[i][1]]
	for t in L[i][1]:
		L[t][1].remove(i)
print(D)


mod = 10 ** 9 + 7
n = int(input())
w = list(map(int, input().strip().split()))
w.append(0)
adj = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().strip().split())
	a -= 1
	b -= 1
	adj[a].append(b)
	adj[b].append(a)
stack = [(0, n)]
det = 1
while stack:
	(i, p) = stack.pop()
	det *= w[i] - w[p]
	det %= mod
	for j in adj[i]:
		if j == p:
			continue
		stack.append((j, i))
print(det)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


mod = 10 ** 9 + 7
n = int(input())
w = list(map(int, input().strip().split()))
w.append(0)
adj = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().strip().split())
	a -= 1
	b -= 1
	adj[a].append(b)
	adj[b].append(a)
stack = [(0, n)]
det = 1
while stack:
	(i, p) = stack.pop()
	det *= w[i] - w[p]
	det %= mod
	for j in adj[i]:
		if j == p:
			continue
		stack.append((j, i))
print(det)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split())
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


mod = 10 ** 9 + 7
n = int(input())
w = list(map(int, input().split()))
w.append(0)
adj = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	adj[a].append(b)
	adj[b].append(a)
arr = [(0, n)]
det = 1
while arr:
	(i, p) = arr.pop()
	det *= w[i] - w[p]
	det %= mod
	for j in adj[i]:
		if j == p:
			continue
		arr.append((j, i))
print(det)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


import collections, sys
MOD = 1000000007

def dfs_compute(tree, weights, root):
	visited = set()
	stack = [(-1, root)]
	product = 1
	while stack:
		(parent, node) = stack.pop()
		if node not in visited:
			visited.add(node)
			product *= weights[node - 1] - (weights[parent - 1] if parent > -1 else 0)
			product %= MOD
			for child in tree[node] - visited:
				stack.append((node, child))
	return product
N = int(sys.stdin.readline())
W = list(map(int, sys.stdin.readline().split()))
tree = collections.defaultdict(set)
for _ in range(N - 1):
	(x, y) = list(map(int, sys.stdin.readline().split()))
	tree[x].add(y)
	tree[y].add(x)
print(dfs_compute(tree, W, 1))


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


import collections, sys
MOD = 1000000007

def dfs_compute(tree, weights, root):
	visited = set()
	stack = [(-1, root)]
	product = 1
	while stack:
		(parent, node) = stack.pop()
		if node not in visited:
			visited.add(node)
			product *= weights[node - 1] - (weights[parent - 1] if parent > -1 else 0)
			product %= MOD
			for child in tree[node] - visited:
				stack.append((node, child))
	return product
N = int(sys.stdin.readline())
W = list(map(int, sys.stdin.readline().split()))
tree = collections.defaultdict(set)
for _ in range(N - 1):
	(x, y) = list(map(int, sys.stdin.readline().split()))
	tree[x].add(y)
	tree[y].add(x)
print(dfs_compute(tree, W, 1))


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


import collections, sys
MOD = 1000000007

def dfs_compute(tree, weights, root):
	visited = set()
	stack = [(-1, root)]
	product = 1
	while stack:
		(parent, node) = stack.pop()
		if node not in visited:
			visited.add(node)
			product *= weights[node - 1] - (weights[parent - 1] if parent > -1 else 0)
			product %= MOD
			for child in tree[node] - visited:
				stack.append((node, child))
	return product
N = int(sys.stdin.readline())
W = list(map(int, sys.stdin.readline().split()))
tree = collections.defaultdict(set)
for _ in range(N - 1):
	(x, y) = list(map(int, sys.stdin.readline().split()))
	tree[x].add(y)
	tree[y].add(x)
print(dfs_compute(tree, W, 1))


import collections, sys
MOD = 1000000007

def dfs_compute(tree, weights, root):
	visited = set()
	stack = [(-1, root)]
	product = 1
	while stack:
		(parent, node) = stack.pop()
		if node not in visited:
			visited.add(node)
			product *= weights[node - 1] - (weights[parent - 1] if parent > -1 else 0)
			product %= MOD
			for child in tree[node] - visited:
				stack.append((node, child))
	return product
N = int(sys.stdin.readline())
W = list(map(int, sys.stdin.readline().split()))
tree = collections.defaultdict(set)
for _ in range(N - 1):
	(x, y) = list(map(int, sys.stdin.readline().split()))
	tree[x].add(y)
	tree[y].add(x)
print(dfs_compute(tree, W, 1))


import collections, sys
MOD = 1000000007

def dfs_compute(tree, weights, root):
	visited = set()
	stack = [(-1, root)]
	product = 1
	while stack:
		(parent, node) = stack.pop()
		if node not in visited:
			visited.add(node)
			product *= weights[node - 1] - (weights[parent - 1] if parent > -1 else 0)
			product %= MOD
			for child in tree[node] - visited:
				stack.append((node, child))
	return product
N = int(sys.stdin.readline())
W = list(map(int, sys.stdin.readline().split()))
tree = collections.defaultdict(set)
for _ in range(N - 1):
	(x, y) = list(map(int, sys.stdin.readline().split()))
	tree[x].add(y)
	tree[y].add(x)
print(dfs_compute(tree, W, 1))


import collections, sys
MOD = 1000000007

def dfs_compute(tree, weights, root):
	visited = set()
	stack = [(-1, root)]
	product = 1
	while stack:
		(parent, node) = stack.pop()
		if node not in visited:
			visited.add(node)
			product *= weights[node - 1] - (weights[parent - 1] if parent > -1 else 0)
			product %= MOD
			for child in tree[node] - visited:
				stack.append((node, child))
	return product
N = int(sys.stdin.readline())
W = list(map(int, sys.stdin.readline().split()))
tree = collections.defaultdict(set)
for _ in range(N - 1):
	(x, y) = list(map(int, sys.stdin.readline().split()))
	tree[x].add(y)
	tree[y].add(x)
print(dfs_compute(tree, W, 1))


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


from collections import deque
P = 10 ** 9 + 7

def main():
	n = int(input().strip())
	ws = [int(w) for w in input().split()]
	adj_list = [[] for _ in range(n)]
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		adj_list[a].append(b)
		adj_list[b].append(a)
	res = 1
	visited = set()
	q = deque()
	q.append((0, 0))
	while len(q):
		(u, k) = q.popleft()
		if u in visited:
			continue
		visited.add(u)
		w = ws[u] - k
		res = res * w % P
		for v in adj_list[u]:
			q.append((v, ws[u]))
	print(res)
main()


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def solve(n, tree, ws):
	prev = [0] * n
	prev[0] = -1
	l = [(0, -1)]
	while l:
		t = l.pop()
		(curr, pre) = (t[0], t[1])
		for i in tree[curr]:
			if i != pre:
				l.append((i, curr))
				prev[i] = curr
	out = 1
	m = 10 ** 9 + 7
	for i in range(n):
		if prev[i] == -1:
			out = out * ws[i] % m
		else:
			out = out * (ws[i] - ws[prev[i]]) % m
	return out
n = int(input())
ws = list(map(int, input().strip().split(' ')))
tree = []
for _ in range(n):
	tree.append([])
for i in range(n - 1):
	inp = list(map(int, input().strip().split(' ')))
	tree[inp[0] - 1].append(inp[1] - 1)
	tree[inp[1] - 1].append(inp[0] - 1)
print(solve(n, tree, ws))


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)


def walk_p(idx, prev):
	cur = idx
	next = [(idx, -1)]
	while len(next) > 0:
		(cur, prev) = next.pop()
		for n in ns[cur]:
			if n == prev:
				continue
			pv[n] = cur
			next.append((n, cur))
n = int(input())
ws = list(map(int, input().split(' ')))
ns = dict([(i, []) for i in range(n)])
for _ in range(n - 1):
	(x, y) = map(lambda x: int(x) - 1, input().split(' '))
	ns[x].append(y)
	ns[y].append(x)
pv = {}
walk_p(0, -1)
ans = 1
m = 10 ** 9 + 7
for i in range(n):
	v = ws[i] - (ws[pv[i]] if i != 0 else 0)
	ans = ans * v % m
print(ans)