Your city has n junctions. There are m one-way roads between the junctions. As a mayor of the city, you have to ensure the security of all the junctions.

To ensure the security, you have to build some police checkposts. Checkposts can only be built in a junction. A checkpost at junction i can protect junction j if either i = j or the police patrol car can go to j from i and then come back to i.

Building checkposts costs some money. As some areas of the city are more expensive than others, building checkpost at some junctions might cost more money than other junctions.

You have to determine the minimum possible money needed to ensure the security of all the junctions. Also you have to find the number of ways to ensure the security in minimum price and in addition in minimum number of checkposts. Two ways are different if any of the junctions contains a checkpost in one of them and do not contain in the other.


-----Input-----

In the first line, you will be given an integer n, number of junctions (1 ≤ n ≤ 10^5). In the next line, n space-separated integers will be given. The i^{th} integer is the cost of building checkpost at the i^{th} junction (costs will be non-negative and will not exceed 10^9).

The next line will contain an integer m (0 ≤ m ≤ 3·10^5). And each of the next m lines contains two integers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n; u ≠ v). A pair u_{i}, v_{i} means, that there is a one-way road which goes from u_{i} to v_{i}. There will not be more than one road between two nodes in the same direction.


-----Output-----

Print two integers separated by spaces. The first one is the minimum possible money needed to ensure the security of all the junctions. And the second one is the number of ways you can ensure the security modulo 1000000007 (10^9 + 7).


-----Examples-----
Input
3
1 2 3
3
1 2
2 3
3 2

Output
3 1

Input
5
2 8 0 6 0
6
1 4
1 3
2 4
3 4
4 5
5 1

Output
8 2

Input
10
1 3 2 2 1 3 1 4 10 10
12
1 2
2 3
3 1
3 4
4 5
5 6
5 7
6 4
7 3
8 9
9 10
10 9

Output
15 6

Input
2
7 91
2
1 2
2 1

Output
7 1

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Amortized analysis

Graph traversal
Skill types: Amortized analysis

Starter code:

Solutions:
def main():
	from bisect import bisect_left as bl, bisect_right as br, insort
	import sys, math
	from collections import defaultdict as dd, deque

	def data():
		return sys.stdin.readline().strip()

	def mdata():
		return list(map(int, data().split()))
	out = sys.stdout.write
	INF = float('INF')
	mod = int(1000000000.0) + 7

	def kosaraju():
		stack = []
		s = []
		vis = [0] * n
		for i in range(n):
			if vis[i] == 0:
				s.append(i)
				while s:
					a = s[-1]
					if vis[a] == 1:
						stack.append(s.pop())
						vis[a] = 2
						continue
					elif vis[a] == 2:
						s.pop()
						continue
					vis[a] = 1
					for i in g[a]:
						if vis[i] == 0:
							s.append(i)
		stack = stack[::-1]
		comp = []
		vis = [0] * n
		ans1 = 0
		ans2 = 1
		for i in stack:
			if vis[i] == 0:
				d = dd(int)
				s.append(i)
				while s:
					a = s[-1]
					if vis[a] == 1:
						d[c[s.pop()]] += 1
						vis[a] = 2
						continue
					elif vis[a] == 2:
						s.pop()
						continue
					vis[a] = 1
					for i in g1[a]:
						if vis[i] == 0:
							s.append(i)
				min1 = min(d.keys())
				ans1 += min1
				ans2 = ans2 * d[min1] % mod
		return (ans1, ans2)
	n = int(data())
	c = mdata()
	m = int(data())
	g = [set() for i in range(n)]
	g1 = [set() for i in range(n)]
	for i in range(m):
		(u, v) = mdata()
		g[u - 1].add(v - 1)
		g1[v - 1].add(u - 1)
	(ans1, ans2) = kosaraju()
	print(ans1, ans2)

def __starting_point():
	main()
__starting_point()


__author__ = 'Gleb'
from time import time
from collections import defaultdict
from bisect import bisect_left, bisect_right
(n, m) = (int(input()) + 1, 1000000007)
(q, p) = ([[] for i in range(n)], [[] for i in range(n)])
w = [0] + list(map(int, input().split()))
for i in range(int(input())):
	(u, v) = list(map(int, input().split()))
	p[u].append(v)
	q[v].append(u)
r = set((i for i in range(1, n) if not p[i] or not q[i]))
(s, t) = (0, 1)
while r:
	i = r.pop()
	s += w[i]
	for j in p[i]:
		q[j].remove(i)
		if not q[j]:
			r.add(j)
	for j in q[i]:
		p[j].remove(i)
		if not p[j]:
			r.add(j)
r = set((i for i in range(1, n) if p[i] and q[i]))
while r:
	i = r.pop()
	h = p[i]
	(d, k) = (w[i], 1)
	while h:
		i = h.pop()
		if not i in r:
			continue
		r.remove(i)
		h += p[i]
		if w[i] == d:
			k += 1
		elif w[i] < d:
			(d, k) = (w[i], 1)
	s += d
	t = t * k % m
print(s, t)


import sys
read = lambda f=int: list(map(f, sys.stdin.readline().split()))
array = lambda *ds: [array(*ds[1:]) for _ in range(ds[0])] if ds else 0

def main():
	(N,) = read()
	cost = tuple(read())
	(E,) = read()
	es = [tuple(read()) for _ in range(E)]

	class Node:

		def __init__(self, name):
			self.name = name
			self.index = None
			self.lowlink = None
			self.adj = []
			self.on_stack = False
	vs = [Node(i) for i in range(N)]
	for (v, w) in es:
		vs[v - 1].adj.append(vs[w - 1])
	i = 0
	stack = []
	call_stack = []
	comps = []
	for v in vs:
		if v.index is None:
			call_stack.append((v, 0))
			while call_stack:
				(v, pi) = call_stack.pop()
				if pi == 0:
					v.index = i
					v.lowlink = i
					i += 1
					stack.append(v)
					v.on_stack = True
				if pi > 0:
					prev = v.adj[pi - 1]
					v.lowlink = min(v.lowlink, prev.lowlink)
				while pi < len(v.adj) and v.adj[pi].index is not None:
					w = v.adj[pi]
					if w.on_stack:
						v.lowlink = min(v.lowlink, w.index)
					pi += 1
				if pi < len(v.adj):
					w = v.adj[pi]
					assert w.index is None
					call_stack.append((v, pi + 1))
					call_stack.append((w, 0))
					continue
				if v.lowlink == v.index:
					comp = []
					while True:
						w = stack.pop()
						w.on_stack = False
						comp.append(w.name)
						if w is v:
							break
					comps.append(comp)
	res = 0
	ways = 1
	for comp in comps:
		c = min((cost[v] for v in comp))
		res += c
		ways *= sum((1 for v in comp if cost[v] == c))
		ways %= 10 ** 9 + 7
	print(res, ways)
main()


from sys import stdin

def main():
	(n, costs) = (int(input()), list(map(int, input().split())))
	input()
	(chlds, prnts) = ([[] for _ in range(n)], [[] for _ in range(n)])
	for total in stdin.read().splitlines():
		(u, v) = list(map(int, total.split()))
		chlds[u - 1].append(v - 1)
		prnts[v - 1].append(u - 1)
	(avail, order) = ([True] * n, [])
	for (u, f) in enumerate(avail):
		if f:
			(avail[u], stack) = (False, [u, prnts[u]])
			while stack:
				while stack[-1]:
					u = stack[-1].pop()
					if avail[u]:
						avail[u] = False
						stack.append(u)
						stack.append(prnts[u])
				del stack[-1]
				order.append(stack.pop())
	(avail, res, cnt, ways) = ([True] * n, 0, 0, 1)
	while order:
		u = order.pop()
		if avail[u]:
			(avail[u], stack, cst, cnt) = (False, chlds[u], costs[u], 0)
			while stack:
				u = stack.pop()
				if avail[u]:
					avail[u] = False
					if cst > costs[u]:
						(cst, cnt) = (costs[u], 0)
					elif cst == costs[u]:
						cnt += 1
					stack += chlds[u]
			res += cst
			if cnt:
				ways = ways * (cnt + 1) % 1000000007
	print(res, ways)

def __starting_point():
	main()
__starting_point()


from collections import defaultdict, deque, Counter, OrderedDict
from heapq import heappop, heappush
import bisect, sys, threading
mod = 10 ** 9 + 7

def dfs_order(i, visited, G, order):
	if visited[i]:
		return
	visited[i] = 1
	for j in G[i]:
		dfs_order(j, visited, G, order)
	order.append(i)

def dfs_scc(leader, s, RG, visited, comp, cost):
	if visited[s]:
		return
	visited[s] = 1
	for j in RG[s]:
		dfs_scc(leader, j, RG, visited, comp, cost)
	comp[leader].append(cost[s])

def main():
	n = int(input())
	cost = [0] + [int(i) for i in input().split()]
	m = int(input())
	G = [[] for i in range(n + 1)]
	RG = [[] for i in range(n + 1)]
	for i in range(m):
		(a, b) = map(int, input().split())
		G[a].append(b)
		RG[b].append(a)
	order = deque()
	visited = [0] * (n + 1)
	for i in range(1, n + 1):
		if not visited[i]:
			dfs_order(i, visited, G, order)
	visited = [0] * (n + 1)
	comp = defaultdict(list)
	while order:
		now = order.pop()
		if not visited[now]:
			dfs_scc(now, now, RG, visited, comp, cost)
	(ans1, ans2) = (0, 1)
	for (k, v) in comp.items():
		v = sorted(v)
		ans1 += v[0]
		poss = bisect.bisect_right(v, v[0])
		ans2 = (ans2 * poss + mod) % mod
	print(ans1, ans2)

def __starting_point():
	sys.setrecursionlimit(200000)
	threading.stack_size(10240000)
	thread = threading.Thread(target=main)
	thread.start()
__starting_point()


MOD = int(1000000000.0) + 7
n = int(input())
w = [0] + list(map(int, input().split()))
q = [[] for i in range(n + 1)]
p = [[] for i in range(n + 1)]
m = int(input())
edges = [list(map(int, input().split())) for _ in range(m)]
for (u, v) in edges:
	p[u].append(v)
	q[v].append(u)
(s, t) = (0, 1)
r = set((i for i in range(1, n + 1) if not p[i] or not q[i]))
while r:
	i = r.pop()
	s += w[i]
	for j in p[i]:
		q[j].remove(i)
		if not q[j]:
			r.add(j)
	for j in q[i]:
		p[j].remove(i)
		if not p[j]:
			r.add(j)
r = set((i for i in range(1, n + 1) if p[i] and q[i]))
while r:
	i = r.pop()
	h = p[i]
	(d, k) = (w[i], 1)
	while h:
		i = h.pop()
		if i not in r:
			continue
		r.remove(i)
		h += p[i]
		if w[i] == d:
			k += 1
		elif w[i] < d:
			(d, k) = (w[i], 1)
	s += d
	t = t * k % MOD
print(s, t)


from sys import stdin
input = stdin.readline

def put():
	return map(int, input().split())

def dfs1():
	s = []
	vis = [0] * (n + 1)
	for i in range(1, n + 1):
		if vis[i] == 0:
			s.append(i)
			while s:
				a = s[-1]
				if vis[a] == 1:
					arr.append(s.pop())
					vis[a] = 2
					continue
				elif vis[a] == 2:
					s.pop()
					continue
				vis[a] = 1
				for i in graph[a]:
					if vis[i] == 0:
						s.append(i)

def dfs2(i):
	s = [i]
	r = []
	vis2[i] = 1
	while s:
		i = s.pop()
		r.append(i)
		for j in revg[i]:
			if not vis2[j]:
				s.append(j)
				vis2[j] = 1
	return r
mod = int(1000000000.0) + 7
n = int(input())
graph = [[] for _ in range(n + 1)]
revg = [[] for _ in range(n + 1)]
(arr, ans) = ([], 0)
(vis1, vis2) = ([0] * (n + 1), [0] * (n + 1))
l = list(put())
m = int(input())
for _ in range(m):
	(x, y) = put()
	graph[x].append(y)
	revg[y].append(x)
dfs1()
c = 1
arr.reverse()
for i in arr:
	if not vis2[i]:
		x = 0
		r = dfs2(i)
		tmp = mod
		for j in r:
			tmp = min(tmp, l[j - 1])
		for j in r:
			if tmp == l[j - 1]:
				x += 1
		c = c * x % mod % mod
		ans += tmp
print(ans, c)


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import time
start_time = time.time()
import collections as col
import math, string
from functools import reduce

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 10 ** 9 + 7

def solve():
	N = getInt()
	C = getInts()
	M = getInt()
	graph = col.defaultdict(set)
	graph2 = col.defaultdict(set)

	def bootstrap(f, stack=[]):

		def wrappedfunc(*args, **kwargs):
			if stack:
				return f(*args, **kwargs)
			else:
				to = f(*args, **kwargs)
				while True:
					if type(to) is GeneratorType:
						stack.append(to)
						to = next(to)
					else:
						stack.pop()
						if not stack:
							break
						to = stack[-1].send(to)
				return to
		return wrappedfunc

	@bootstrap
	def dfs2(i, visited):
		tmp = []
		visited[i] = True
		connected_components[-1].append(i)
		for neighbour in graph2[i]:
			if not visited[neighbour]:
				yield dfs2(neighbour, visited)
		yield

	@bootstrap
	def dfs(i, visited, stack):
		visited[i] = True
		for neighbour in graph[i]:
			if not visited[neighbour]:
				yield dfs(neighbour, visited, stack)
		stack.append(i)
		yield

	@bootstrap
	def getCCs():
		stack = []
		visited = [False] * N
		for i in range(N):
			if not visited[i]:
				yield dfs(i, visited, stack)
		visited = [False] * N
		while stack:
			i = stack.pop()
			if not visited[i]:
				connected_components.append([])
				yield dfs2(i, visited)
		yield
	for m in range(M):
		(U, V) = getInts()
		U -= 1
		V -= 1
		graph[U].add(V)
		graph2[V].add(U)
	connected_components = []
	getCCs()
	min_cost = 0
	num_ways = 1
	for comp in connected_components:
		best = 10 ** 9 + 1
		best_count = 1
		for el in comp:
			if C[el] == best:
				best_count += 1
			elif C[el] < best:
				best = C[el]
				best_count = 1
		num_ways *= best_count
		num_ways %= MOD
		min_cost += best
	print(min_cost, num_ways)
	return
solve()


from collections import *
from sys import setrecursionlimit, stdin
import threading
mod = 1000000007

def arr_inp(n):
	if n == 1:
		return [int(x) for x in stdin.readline().split()]
	elif n == 2:
		return [float(x) for x in stdin.readline().split()]
	else:
		return list(stdin.readline()[:-1])

def main():

	class graph:

		def __init__(self, gdict=None):
			if gdict is None:
				gdict = defaultdict(list)
			(self.gdict, self.edges, self.l) = (gdict, [], defaultdict(int))

		def addEdge(self, node1, node2, w=None):
			self.gdict[node1].append(node2)

		def scc_utils(self, v):
			(self.disc[v], self.low[v], self.stack[v]) = (self.time, self.time, 1)
			self.time += 1
			self.st.append(v)
			for i in self.gdict[v]:
				if self.disc[i] == -1:
					self.scc_utils(i)
					self.low[v] = min(self.low[v], self.low[i])
				elif self.stack[i]:
					self.low[v] = min(self.low[v], self.disc[i])
			if self.low[v] == self.disc[v]:
				(node, mem) = (-1, defaultdict(int))
				while node != v:
					node = self.st.pop()
					self.stack[node] = 0
					mem[cost[node - 1]] += 1
				self.count += min(mem)
				self.mi = self.mi % mod * (mem[min(mem)] % mod) % mod

		def scc(self, n):
			(self.time, self.count, self.mi) = (0, 0, 1)
			(self.disc, self.low, self.stack, self.st) = ([-1] * (n + 1), [-1] * (n + 1), [0] * (n + 1), [])
			for i in range(1, n + 1):
				if self.disc[i] == -1:
					self.scc_utils(i)
			print(self.count, self.mi)
	(n, cost, m, g) = (int(input()), arr_inp(1), int(input()), graph())
	for i in range(m):
		(u, v) = arr_inp(1)
		g.addEdge(u, v)
	g.scc(n)

def __starting_point():
	setrecursionlimit(50000)
	threading.stack_size(102400000)
	thread = threading.Thread(target=main)
	thread.start()
__starting_point()


import os
import sys
from io import BytesIO, IOBase
mod = 10 ** 9 + 7

def main():
	n = int(input())
	cost = list(map(int, input().split()))
	m = int(input())
	graph = [[] for _ in range(n)]
	revgraph = [[] for _ in range(n)]
	for _ in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		graph[u].append(v)
		revgraph[v].append(u)
	stack = []
	idx = [0] * n
	temp = []
	visited = [0] * n
	for i in range(n):
		if visited[i]:
			continue
		visited[i] = 1
		temp = [i]
		while temp:
			x = temp[-1]
			y = idx[x]
			if y == len(graph[x]):
				stack.append(temp.pop())
			else:
				z = graph[x][y]
				if visited[z] == 0:
					visited[z] = 1
					temp.append(z)
				idx[x] += 1
	result = [0]
	ans = [1]
	visited = [0] * n
	temp = []
	idx = [0] * n
	while stack:
		z = stack.pop()
		if visited[z]:
			continue
		visited[z] = 1
		temp = [z]
		mmcost = float('inf')
		mmno = 0
		while temp:
			x = temp[-1]
			y = idx[x]
			if y == len(revgraph[x]):
				k = temp.pop()
				if cost[k] < mmcost:
					mmcost = cost[k]
					mmno = 1
				elif cost[k] == mmcost:
					mmno += 1
			else:
				t = revgraph[x][y]
				if visited[t] == 0:
					visited[t] = 1
					temp.append(t)
				idx[x] += 1
		result.append(mmcost + result[-1])
		ans.append(ans[-1] * mmno % mod)
	print(result[-1], ans[-1])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from collections import defaultdict

def dfs(d, visited, l, i):
	visited[i] = True
	for j in d[i + 1]:
		if not visited[j - 1]:
			dfs(d, visited, l, j - 1)
	l.append(i + 1)

def dfs1(d, visited, x, i):
	visited[i - 1] = True
	x.add(i)
	for j in d[i]:
		if not visited[j - 1]:
			dfs1(d, visited, x, j)

def main():
	n = int(input())
	a = list(map(int, input().split()))
	d = defaultdict(list)
	d1 = defaultdict(list)
	for i in range(int(input())):
		(u, v) = list(map(int, input().split()))
		d[u].append(v)
		d1[v].append(u)
	l = []
	visited = [False] * n
	for i in range(n):
		if not visited[i]:
			dfs(d, visited, l, i)
	visited = [False] * n
	l1 = []
	while l:
		i = l.pop()
		if not visited[i - 1]:
			x = set()
			dfs1(d1, visited, x, i)
			l1.append(x)
	(cost, ways) = (0, 1)
	for i in l1:
		x = list(i)
		z = a[min(x, key=lambda x: a[x - 1]) - 1]
		cost = cost + z
		y = 0
		for i in x:
			if a[i - 1] == z:
				y += 1
		ways = max(y, 1) * ways % (10 ** 9 + 7)
	print(cost, ways)
import sys, threading
max_recur_size = 10 ** 5 + 10000
max_stack_size = max_recur_size * 500
sys.setrecursionlimit(max_recur_size)
threading.stack_size(max_stack_size)
thread = threading.Thread(target=main)
thread.start()


import os, sys
from io import BytesIO, IOBase

def tarjan(n, path):
	(visi, poi, comp, low, start, time, num) = ([0] * n, [0] * n, [0] * n, [0] * n, [0] * n, 0, 1)
	for i in range(n):
		if visi[i]:
			continue
		(st, visi[i], st1) = ([i], 2, [i])
		while len(st):
			(x, y) = (st[-1], path[st[-1]])
			while poi[x] != len(y) and visi[y[poi[x]]]:
				if visi[y[poi[x]]] == 2:
					low[x] = min(low[x], start[y[poi[x]]])
				poi[x] += 1
			if poi[x] == len(y):
				st.pop()
				if len(st):
					low[st[-1]] = min(low[st[-1]], low[x])
				if low[x] == start[x]:
					while st1[-1] != x:
						visi[st1[-1]] = 1
						comp[st1.pop()] = num
					visi[st1[-1]] = 1
					comp[st1.pop()] = num
					num += 1
			else:
				time += 1
				i = y[poi[x]]
				st.append(i)
				st1.append(i)
				(start[i], low[i], visi[i]) = (time, time, 2)
	return comp

def main():
	from collections import Counter, defaultdict
	mod = 10 ** 9 + 7
	n = int(input())
	cost = list(map(int, input().split()))
	path = [[] for _ in range(n)]
	for _ in range(int(input())):
		(a, b) = map(lambda xx: int(xx) - 1, input().split())
		path[a].append(b)
	comp = tarjan(n, path)
	(mon, ti) = (0, 1)
	c = defaultdict(Counter)
	for i in range(n):
		c[comp[i]][cost[i]] += 1
	for i in c:
		z = min(c[i])
		mon += z
		ti = ti * c[i][z] % mod
	print(mon, ti)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from sys import stdin

def main():
	n = int(input())
	costs = list(map(int, input().split()))
	input()
	(chlds, prnts) = ([[] for _ in range(n)], [[] for _ in range(n)])
	for total in stdin.read().splitlines():
		(u, v) = map(int, total.split())
		chlds[u - 1].append(v - 1)
		prnts[v - 1].append(u - 1)
	(total, ways, childless, orphans) = (sum(costs), 1, [], [])
	for (i, cc, pp) in zip(range(n), chlds, prnts):
		if not (cc or pp):
			costs[i] = 0
		elif not cc:
			childless.append(i)
		elif not pp:
			orphans.append(i)
	while childless:
		u = childless.pop()
		costs[u] = 0
		for v in prnts[u]:
			chlds[v].remove(u)
			if not chlds[v]:
				childless.append(v)
	while orphans:
		u = orphans.pop()
		costs[u] = 0
		for v in chlds[u]:
			prnts[v].remove(u)
			if not prnts[v]:
				orphans.append(v)
	total -= sum(costs)
	pool = {u for u in range(n) if prnts[u] and chlds[u]}
	while pool:
		u = pool.pop()
		pp = prnts[u]
		(cost, cnt) = (costs[u], 1)
		while pp:
			u = pp.pop()
			if u in pool:
				pool.remove(u)
				pp += prnts[u]
				if costs[u] == cost:
					cnt += 1
				elif costs[u] < cost:
					(cost, cnt) = (costs[u], 1)
		total += cost
		ways = ways * cnt % 1000000007
	print(total, ways)
main()


from collections import *
from sys import setrecursionlimit, stdin
import threading
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
mod = 1000000007
rints = lambda : [int(x) for x in stdin.readline().split()]

class graph:

	def __init__(self, gdict=None):
		if gdict is None:
			gdict = defaultdict(list)
		(self.gdict, self.edges, self.l) = (gdict, [], defaultdict(int))

	def addEdge(self, node1, node2, w=None):
		self.gdict[node1].append(node2)

	@bootstrap
	def scc_utils(self, v):
		(self.disc[v], self.low[v], self.stack[v]) = (self.time, self.time, 1)
		self.time += 1
		self.st.append(v)
		for i in self.gdict[v]:
			if self.disc[i] == -1:
				yield self.scc_utils(i)
				self.low[v] = min(self.low[v], self.low[i])
			elif self.stack[i]:
				self.low[v] = min(self.low[v], self.disc[i])
		if self.low[v] == self.disc[v]:
			(node, mem) = (-1, defaultdict(int))
			while node != v:
				node = self.st.pop()
				self.stack[node] = 0
				mem[cost[node - 1]] += 1
			self.count += min(mem)
			self.mi = self.mi % mod * (mem[min(mem)] % mod) % mod
		yield

	def scc(self, n):
		(self.time, self.count, self.mi) = (0, 0, 1)
		(self.disc, self.low, self.stack, self.st) = ([-1] * (n + 1), [-1] * (n + 1), [0] * (n + 1), [])
		for i in range(1, n + 1):
			if self.disc[i] == -1:
				self.scc_utils(i)
		print(self.count, self.mi)
(n, cost, m, g) = (int(input()), rints(), int(input()), graph())
for i in range(m):
	(u, v) = rints()
	g.addEdge(u, v)
g.scc(n)


import sys
input = sys.stdin.readline

def get_scc_nonrec(n, graph, reverse):
	x = []
	flag = [0] * n
	(traversed, registered) = (1, 2)
	for i in range(n):
		if flag[i]:
			continue
		stack = [i]
		while stack:
			vf = stack[-1]
			if flag[vf] & registered:
				stack.pop()
				continue
			if not flag[vf] & traversed:
				flag[vf] |= traversed
				for vt in graph[vf][::-1]:
					if not flag[vt] & traversed:
						stack.append(vt)
			elif not flag[vf] & registered:
				x.append(stack.pop())
				flag[vf] |= registered
	x.reverse()
	scc = [-1] * n
	m = 0
	for i in x:
		if scc[i] >= 0:
			continue
		scc[i] = m
		stack = [i]
		while stack:
			vf = stack.pop()
			for vt in reverse[vf]:
				if scc[vt] < 0:
					stack.append(vt)
					scc[vt] = m
		m += 1
	return (m, scc)
mod = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
g = [[] for i in range(n)]
rg = [[] for i in range(n)]
m = int(input())
for _ in range(m):
	(u, v) = map(int, input().split())
	g[u - 1].append(v - 1)
	rg[v - 1].append(u - 1)
(label, group) = get_scc_nonrec(n, g, rg)
mem = [[] for i in range(label + 1)]
for i in range(n):
	mem[group[i]].append(a[i])
min_score = 0
pattern = 1
for i in range(label + 1):
	if not mem[i]:
		continue
	x = min(mem[i])
	c = mem[i].count(x)
	pattern *= c
	pattern %= mod
	min_score += x
print(min_score, pattern)


from collections import defaultdict
from sys import setrecursionlimit
from collections import Counter
setrecursionlimit(10 ** 5)
import threading
from sys import stdin
input = stdin.readline

def dfs(node, vis, g, ans):
	vis[node] = 1
	for i in g[node]:
		if vis[i] == 0:
			dfs(i, vis, g, ans)
	ans.append(node)
	return

def dfs2(node, vis, g, component):
	vis[node] = 1
	component.append(node)
	for i in g[node]:
		if vis[i] == 0:
			dfs2(i, vis, g, component)

def main():
	n = int(input())
	g = defaultdict(list)
	graph_reversed = defaultdict(list)
	lst = list(map(int, input().strip().split()))
	for i in range(int(input())):
		(x, y) = map(int, input().strip().split())
		g[x].append(y)
		graph_reversed[y].append(x)
	vis = [0] * (n + 1)
	order = []
	cost = 0
	for ind in range(1, n + 1):
		if vis[ind] == 0:
			dfs(ind, vis, g, order)
	order = order[::-1]
	vis = [0] * (n + 1)
	ans = 0
	total = 1
	for ind in order:
		if vis[ind] == 0:
			component = []
			dfs2(ind, vis, graph_reversed, component)
			ls = [lst[i - 1] for i in component]
			cnt = Counter(ls)
			mn = min(cnt.keys())
			ans += mn
			total = total * cnt[mn] % (10 ** 9 + 7)
	print(ans, total)
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


import sys
read = lambda f=int: list(map(f, sys.stdin.readline().split()))
array = lambda *ds: [array(*ds[1:]) for _ in range(ds[0])] if ds else 0

def main():
	(N,) = read()
	cost = tuple(read())
	(E,) = read()
	es = [tuple(read()) for _ in range(E)]

	class Node:

		def __init__(self, name):
			self.name = name
			self.index = None
			self.lowlink = None
			self.adj = []
			self.on_stack = False
	vs = [Node(i) for i in range(N)]
	for (v, w) in es:
		vs[v - 1].adj.append(vs[w - 1])

	def scc(vs):
		i = 0
		stack = []
		call_stack = []
		comps = []
		for v in vs:
			if v.index is None:
				call_stack.append((v, 0))
				while call_stack:
					(v, pi) = call_stack.pop()
					if pi == 0:
						v.index = i
						v.lowlink = i
						i += 1
						stack.append(v)
						v.on_stack = True
					if pi > 0:
						prev = v.adj[pi - 1]
						v.lowlink = min(v.lowlink, prev.lowlink)
					while pi < len(v.adj) and v.adj[pi].index is not None:
						w = v.adj[pi]
						if w.on_stack:
							v.lowlink = min(v.lowlink, w.index)
						pi += 1
					if pi < len(v.adj):
						w = v.adj[pi]
						call_stack.append((v, pi + 1))
						call_stack.append((w, 0))
						continue
					if v.lowlink == v.index:
						comp = []
						while True:
							w = stack.pop()
							w.on_stack = False
							comp.append(w.name)
							if w is v:
								break
						comps.append(comp)
		return comps

	def scc2(vs):
		result = []
		stack = []
		low = {}
		graph = {v.name: [w.name for w in v.adj] for v in vs}

		def visit(node):
			if node in low:
				return
			num = len(low)
			low[node] = num
			stack_pos = len(stack)
			stack.append(node)
			for successor in graph[node]:
				visit(successor)
				low[node] = min(low[node], low[successor])
			if num == low[node]:
				component = tuple(stack[stack_pos:])
				del stack[stack_pos:]
				result.append(component)
				for item in component:
					low[item] = len(graph)
		for v in graph:
			visit(v)
		return result

	def scc3(vs):
		graph = {v.name: [w.name for w in v.adj] for v in vs}
		result = []
		stack = []
		low = {}
		call_stack = []
		for v in graph:
			call_stack.append((v, 0, len(low)))
			while call_stack:
				(v, pi, num) = call_stack.pop()
				if pi == 0:
					if v in low:
						continue
					low[v] = num
					stack.append(v)
				if pi > 0:
					low[v] = min(low[v], low[graph[v][pi - 1]])
				if pi < len(graph[v]):
					call_stack.append((v, pi + 1, num))
					call_stack.append((graph[v][pi], 0, len(low)))
					continue
				if num == low[v]:
					comp = []
					while True:
						comp.append(stack.pop())
						low[comp[-1]] = len(graph)
						if comp[-1] == v:
							break
					result.append(comp)
		return result
	res = 0
	ways = 1
	for comp in scc3(vs):
		c = min((cost[v] for v in comp))
		res += c
		ways *= sum((1 for v in comp if cost[v] == c))
		ways %= 10 ** 9 + 7
	print(res, ways)
main()


import sys
input = sys.stdin.readline

def scc(N, G, RG):
	order = []
	state = [0] * N
	(traversed, registered) = (1, 2)
	for i in range(n):
		if state[i]:
			continue
		stack = [i]
		while stack:
			v = stack[-1]
			if state[v] & registered:
				stack.pop()
				continue
			if not state[v] & traversed:
				state[v] |= traversed
				for to in G[v][::-1]:
					if not state[to] & traversed:
						stack.append(to)
			elif not state[v] & registered:
				order.append(stack.pop())
				state[v] |= registered
	order.reverse()
	group = [-1] * n
	label = 0
	for s in order:
		if group[s] >= 0:
			continue
		group[s] = label
		stack = [s]
		while stack:
			v = stack.pop()
			for to in RG[v]:
				if group[to] < 0:
					stack.append(to)
					group[to] = label
		label += 1
	return (label, group)
mod = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
g = [[] for i in range(n)]
rg = [[] for i in range(n)]
m = int(input())
for _ in range(m):
	(u, v) = map(int, input().split())
	g[u - 1].append(v - 1)
	rg[v - 1].append(u - 1)
(label, group) = scc(n, g, rg)
mem = [[] for i in range(label + 1)]
for i in range(n):
	mem[group[i]].append(a[i])
min_score = 0
pattern = 1
for i in range(label + 1):
	if not mem[i]:
		continue
	x = min(mem[i])
	c = mem[i].count(x)
	pattern *= c
	pattern %= mod
	min_score += x
print(min_score, pattern)


import sys, os, io
from sys import stdin
import math
from collections import defaultdict
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
alphabets = list('abcdefghijklmnopqrstuvwxyz')
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieveForSmallestPrimeFactor():
	MAXN = 100001
	spf = [0 for i in range(MAXN)]
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, math.ceil(math.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
	return spf

def getPrimeFactorizationLOGN(x):
	spf = sieveForSmallestPrimeFactor()
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def si():
	return input()

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = ii()
checkpost = li()
m = ii()
adj = [[] for i in range(n)]
Tadj = [[] for i in range(n)]
for i in range(m):
	(u, v) = li()
	u -= 1
	v -= 1
	adj[u].append(v)
	Tadj[v].append(u)
st = []
vis = [False] * n

@bootstrap
def dfs(node, parent):
	for kid in adj[node]:
		if kid != parent and vis[kid] == False:
			vis[kid] = True
			yield dfs(kid, node)
	st.append(node)
	yield

@bootstrap
def dfs2(node, parent, cur, d):
	cur[0] = min(cur[0], checkpost[node])
	d[checkpost[node]] += 1
	for kid in Tadj[node]:
		if kid != parent and vis[kid] == False:
			vis[kid] = True
			yield dfs2(kid, node, cur, d)
	yield
for i in range(n):
	if vis[i] == False:
		dfs(i, -1)
vis = [False] * n
ans = 0
mod = int(1000000000.0) + 7
cnt = 1
while st:
	node = st.pop(-1)
	while vis[node] == True and st:
		node = st.pop(-1)
	if vis[node] == True:
		break
	d = defaultdict(lambda : 0)
	vis[node] = True
	cur = [float('inf')]
	dfs2(node, -1, cur, d)
	cnt *= d[cur[0]]
	cnt %= mod
	ans += cur[0]
print(ans, cnt)


mod = 10 ** 9 + 7
import sys
input = sys.stdin.readline
from collections import deque

class Graph(object):

	def __init__(self, n, d):
		self.n = n
		self.graph = [[] for i in range(n)]
		self.parent = [-1 for i in range(n)]
		self.directed = d

	def addEdge(self, x, y):
		self.graph[x].append(y)
		if not self.directed:
			self.graph[y].append(x)

	def bfs(self, root):
		queue = [root]
		queue = deque(queue)
		vis = [0] * self.n
		while len(queue) != 0:
			element = queue.popleft()
			vis[element] = 1
			for i in self.graph[element]:
				if vis[i] == 0:
					queue.append(i)
					self.parent[i] = element
					vis[i] = 1

	def dfs(self, root, vis):
		stack = [root]
		stack2 = []
		while len(stack) != 0:
			element = stack.pop()
			if vis[element]:
				continue
			vis[element] = 1
			stack2.append(element)
			for i in self.graph[element]:
				if vis[i] == 0:
					self.parent[i] = element
					stack.append(i)
		return (stack2[::-1], vis)

	def dfs2(self, root, vis):
		stack = [root]
		stack2 = []
		cost = 10 ** 18
		count = 0
		while len(stack) != 0:
			element = stack.pop()
			if vis[element]:
				continue
			if costs[element] < cost:
				cost = costs[element]
				count = 1
			elif costs[element] == cost:
				count += 1
			vis[element] = 1
			stack2.append(element)
			for i in self.graph[element]:
				if vis[i] == 0:
					self.parent[i] = element
					stack.append(i)
		return (cost, count, vis)

	def count_scc(self, root):
		vis = [0] * self.n
		stack = []
		for i in range(self.n):
			if not vis[i]:
				(a, vis) = self.dfs(i, vis)
				stack.extend(a)
		g = [[] for i in range(self.n)]
		for i in range(self.n):
			for j in self.graph[i]:
				g[j].append(i)
		self.graph = g
		vis = [0] * self.n
		a1 = 0
		a2 = 1
		count = 0
		while len(stack) != 0:
			e = stack.pop()
			if not vis[e]:
				(a, b, vis) = self.dfs2(e, vis)
				a1 += a
				count += 1
				a2 = a2 * b % mod
		if a1 == 602483:
			print(count)
			print(vis)
			exit()
		return (a1, a2)
(n, m) = (int(input()) + 1, 1000000007)
(q, p) = ([[] for i in range(n)], [[] for i in range(n)])
w = [0] + list(map(int, input().split()))
for i in range(int(input())):
	(u, v) = map(int, input().split())
	p[u].append(v)
	q[v].append(u)
r = set((i for i in range(1, n) if not p[i] or not q[i]))
(s, t) = (0, 1)
while r:
	i = r.pop()
	s += w[i]
	for j in p[i]:
		q[j].remove(i)
		if not q[j]:
			r.add(j)
	for j in q[i]:
		p[j].remove(i)
		if not p[j]:
			r.add(j)
r = set((i for i in range(1, n) if p[i] and q[i]))
while r:
	i = r.pop()
	h = p[i]
	(d, k) = (w[i], 1)
	while h:
		i = h.pop()
		if not i in r:
			continue
		r.remove(i)
		h += p[i]
		if w[i] == d:
			k += 1
		elif w[i] < d:
			(d, k) = (w[i], 1)
	s += d
	t = t * k % m
print(s, t)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import ceil, floor
from copy import *
from collections import deque, defaultdict
from collections import Counter as counter
from itertools import combinations
from itertools import permutations as permutate
from bisect import bisect_left as bl
from operator import *
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192
from sys import stderr

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def pow(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def gcd(a, b):
	if a == b:
		return a
	while b > 0:
		(a, b) = (b, a % b)
	return a

def prefix_sum(ar):
	return list(accumulate(ar))

def suffix_sum(ar):
	return list(accumulate(ar[::-1]))[::-1]

def N():
	return int(inp())
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def YES():
	print('YES')

def NO():
	print('NO')

def Yes():
	print('Yes')

def No():
	print('No')
from collections import defaultdict

def numberOfSetBits(i):
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24

class MergeFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n

	def find(self, a):
		to_update = []
		while a != self.parent[a]:
			to_update.append(a)
			a = self.parent[a]
		for b in to_update:
			self.parent[b] = a
		return self.parent[a]

	def merge(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a == b:
			return
		self.num_sets -= 1
		self.parent[a] = b
		self.size[b] += self.size[a]

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets

def lcm(a, b):
	return abs(a // gcd(a, b) * b)

def solve():

	def scc(coupl):
		(SCC, S, P) = ([], [], [])
		depth = [0] * len(coupl)
		stack = list(range(len(coupl)))
		while stack:
			node = stack.pop()
			if node < 0:
				if P[-1] == depth[~node]:
					SCC.append(S[P[-1] - 1:])
					del S[P[-1] - 1:], P[-1]
					for node in SCC[-1]:
						depth[node] = -1
			elif depth[node] > 0:
				while P[-1] > depth[node]:
					P.pop()
			elif depth[node] == 0:
				S.append(node)
				P.append(len(S))
				depth[node] = len(S)
				stack.append(~node)
				stack += coupl[node]
		return SCC[::-1]
	n = N()
	ar = lis()
	m = N()
	g = [[] for _ in range(n)]
	for _ in range(m):
		(a, b) = sep()
		a -= 1
		b -= 1
		g[a].append(b)
	t = scc(g)
	ans = 1
	mod = 10 ** 9 + 7
	m = 0
	d = defaultdict(list)
	for i in range(len(t)):
		tem = [ar[j] for j in t[i]]
		mi = min(tem)
		m += mi
		ans *= tem.count(mi)
		ans %= mod
	print(m, ans)
solve()


from sys import stdin

def main():
	n = int(input())
	costs = list(map(int, input().split()))
	input()
	(chlds, prnts) = ([[] for _ in range(n)], [[] for _ in range(n)])
	for total in stdin.read().splitlines():
		(u, v) = list(map(int, total.split()))
		chlds[u - 1].append(v - 1)
		prnts[v - 1].append(u - 1)
	(total, ways, pool) = (0, 1, {i for i in range(n) if not (prnts[i] and chlds[i])})
	while pool:
		u = pool.pop()
		total += costs[u]
		for v in prnts[u]:
			chlds[v].remove(u)
			if not chlds[v]:
				pool.add(v)
		for v in chlds[u]:
			prnts[v].remove(u)
			if not prnts[v]:
				pool.add(v)
	pool = {u for u in range(n) if prnts[u] and chlds[u]}
	while pool:
		u = pool.pop()
		pp = prnts[u]
		(cost, cnt) = (costs[u], 1)
		while pp:
			u = pp.pop()
			if u in pool:
				pool.remove(u)
				pp += prnts[u]
				if costs[u] == cost:
					cnt += 1
				elif costs[u] < cost:
					(cost, cnt) = (costs[u], 1)
		total += cost
		ways = ways * cnt % 1000000007
	print(total, ways)

def __starting_point():
	main()
__starting_point()


from collections import defaultdict, deque
from bisect import bisect
from sys import setrecursionlimit
from threading import stack_size, Thread
MOD = 10 ** 9 + 7

def dfs_order(i, visited, g, order):
	if visited[i]:
		return
	visited[i] = 1
	for j in g[i]:
		dfs_order(j, visited, g, order)
	order.append(i)

def dfs_scc(leader, s, rg, visited, comp, cost):
	if visited[s]:
		return
	visited[s] = 1
	for j in rg[s]:
		dfs_scc(leader, j, rg, visited, comp, cost)
	comp[leader].append(cost[s])

def main():
	n = int(input())
	cost = [0] + [int(i) for i in input().split()]
	m = int(input())
	g = [[] for i in range(n + 1)]
	rg = [[] for i in range(n + 1)]
	for i in range(m):
		(a, b) = map(int, input().split())
		g[a].append(b)
		rg[b].append(a)
	order = deque()
	visited = [0] * (n + 1)
	for i in range(1, n + 1):
		if not visited[i]:
			dfs_order(i, visited, g, order)
	visited = [0] * (n + 1)
	comp = defaultdict(list)
	while order:
		now = order.pop()
		if not visited[now]:
			dfs_scc(now, now, rg, visited, comp, cost)
	(ans1, ans2) = (0, 1)
	for (key, values) in comp.items():
		values = sorted(values)
		ans1 += values[0]
		position = bisect(values, values[0])
		ans2 = (ans2 * position + MOD) % MOD
	print(ans1, ans2)
setrecursionlimit(MOD)
stack_size(102400000)
t = Thread(target=main)
t.start()