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: interview

Starter code:

Solutions:
__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 = 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 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()

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(102400000)
    thread = threading.Thread(target=main)
    thread.start()
__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()

from collections import defaultdict, deque, Counter, OrderedDict
from heapq import heappop, heappush
import bisect, sys, threading
#2
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 = list(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 list(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()

######
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()

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 = 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 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)
    #print(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)
    #print(comp)

    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()

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 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, childless, orphans = sum(costs), 1, [], []
    for i, cc, pp in zip(list(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)


def __starting_point():
    main()

__starting_point()

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()

__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)



# Made By Mostafa_Khaled


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 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:
        # initialize graph
        def __init__(self, gdict=None):
            if gdict is None:
                gdict = defaultdict(list)
            self.gdict, self.edges, self.l = gdict, [], defaultdict(int)

        # add edge
        def addEdge(self, node1, node2, w=None):
            if w != None:
                self.gdict[node1].append([node2, w])
                self.gdict[node2].append([node1, w])
            else:
                self.gdict[node1].append(node2)
                # self.gdict[node2].append(node1)
            self.edges.append([node1, node2, w])
            self.l[node1] += 1
            self.l[node2] += 1

        def scc_utils(self, v):

            # initilaize time and disc
            self.disc[v], self.low[v], self.stack[v] = self.time, self.time, 1
            self.time += 1
            self.st.append(v)

            # loop edges
            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])

                # print founded scc
            if self.low[v] == self.disc[v]:
                node, mem = -1, defaultdict(int)
                while node != v:
                    node = self.st.pop()
                    # print(node, end=' ')
                    self.stack[node] = 0
                    mem[cost[node - 1]] += 1
                # print(end='\n')

                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(200000)
    threading.stack_size(102400000)
    thread = threading.Thread(target=main)
    thread.start()

__starting_point()

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:
        # initialize graph
        def __init__(self, gdict=None):
            if gdict is None:
                gdict = defaultdict(list)
            self.gdict, self.edges, self.l = gdict, [], defaultdict(int)

        # add edge
        def addEdge(self, node1, node2, w=None):
            if w != None:
                self.gdict[node1].append([node2, w])
                self.gdict[node2].append([node1, w])
            else:
                self.gdict[node1].append(node2)
                # self.gdict[node2].append(node1)
            self.edges.append([node1, node2, w])
            self.l[node1] += 1
            self.l[node2] += 1

        def scc_utils(self, v):

            # initilaize time and disc
            self.disc[v], self.low[v], self.stack[v] = self.time, self.time, 1
            self.time += 1
            self.st.append(v)

            # loop edges
            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])

                # print founded scc
            if self.low[v] == self.disc[v]:
                node, mem = -1, defaultdict(int)
                while node != v:
                    node = self.st.pop()
                    # print(node, end=' ')
                    self.stack[node] = 0
                    mem[cost[node - 1]] += 1
                # print(end='\n')

                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(100000)
    threading.stack_size(102400000)
    thread = threading.Thread(target=main)
    thread.start()

__starting_point()

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:
        # initialize graph
        def __init__(self, gdict=None):
            if gdict is None:
                gdict = defaultdict(list)
            self.gdict, self.edges, self.l = gdict, [], defaultdict(int)

        # add edge
        def addEdge(self, node1, node2, w=None):
            self.gdict[node1].append(node2)
            # self.gdict[node2].append(node1)
            # self.edges.append([node1, node2, w])
            # self.l[node1] += 1
            # self.l[node2] += 1

        def scc_utils(self, v):

            # initilaize time and disc
            self.disc[v], self.low[v], self.stack[v] = self.time, self.time, 1
            self.time += 1
            self.st.append(v)

            # loop edges
            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])

                # print founded scc
            if self.low[v] == self.disc[v]:
                node, mem = -1, defaultdict(int)
                while node != v:
                    node = self.st.pop()
                    # print(node, end=' ')
                    self.stack[node] = 0
                    mem[cost[node - 1]] += 1
                # print(end='\n')

                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(100000)
    threading.stack_size(102400000)
    thread = threading.Thread(target=main)
    thread.start()

__starting_point()

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:
        # initialize graph
        def __init__(self, gdict=None):
            if gdict is None:
                gdict = defaultdict(list)
            self.gdict, self.edges, self.l = gdict, [], defaultdict(int)

        # add edge
        def addEdge(self, node1, node2, w=None):
            self.gdict[node1].append(node2)
            # self.gdict[node2].append(node1)
            # self.edges.append([node1, node2, w])
            # self.l[node1] += 1
            # self.l[node2] += 1

        def scc_utils(self, v):

            # initilaize time and disc
            self.disc[v], self.low[v], self.stack[v] = self.time, self.time, 1
            self.time += 1
            self.st.append(v)

            # loop edges
            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])

                # print founded scc
            if self.low[v] == self.disc[v]:
                node, mem = -1, defaultdict(int)
                while node != v:
                    node = self.st.pop()
                    # print(node, end=' ')
                    self.stack[node] = 0
                    mem[cost[node - 1]] += 1
                # print(end='\n')

                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(80000)
    threading.stack_size(102400000)
    thread = threading.Thread(target=main)
    thread.start()

__starting_point()

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:
        # initialize graph
        def __init__(self, gdict=None):
            if gdict is None:
                gdict = defaultdict(list)
            self.gdict, self.edges, self.l = gdict, [], defaultdict(int)

        # add edge
        def addEdge(self, node1, node2, w=None):
            self.gdict[node1].append(node2)
            # self.gdict[node2].append(node1)
            # self.edges.append([node1, node2, w])
            # self.l[node1] += 1
            # self.l[node2] += 1

        def scc_utils(self, v):

            # initilaize time and disc
            self.disc[v], self.low[v], self.stack[v] = self.time, self.time, 1
            self.time += 1
            self.st.append(v)

            # loop edges
            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])

                # print founded scc
            if self.low[v] == self.disc[v]:
                node, mem = -1, defaultdict(int)
                while node != v:
                    node = self.st.pop()
                    # print(node, end=' ')
                    self.stack[node] = 0
                    mem[cost[node - 1]] += 1
                # print(end='\n')

                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()

def main():

    from bisect import bisect_left as bl, bisect_right as br, insort
    import sys,math
    #from heapq import heapify, heappush, heappop
    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
    # sys.setrecursionlimit(100000)
    INF = float("INF")
    mod = int(1e9)+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()

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 we just recursed on something
                if pi > 0:
                    prev = v.adj[pi-1]
                    v.lowlink = min(v.lowlink, prev.lowlink)
                # Find the next thing to recurse on
                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 we found something with index=None, recurse
                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 # This is important, since later nodes may see it
                        comp.append(w.name)
                        if w is v:
                            break
                    comps.append(comp)

    #print(stack)
    #print(comps)
    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()


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 this is first time we see v
                    if pi == 0:
                        v.index = i
                        v.lowlink = i
                        i += 1
                        stack.append(v)
                        v.on_stack = True
                    # If we just recursed on something
                    if pi > 0:
                        prev = v.adj[pi-1]
                        v.lowlink = min(v.lowlink, prev.lowlink)
                    # Find the next thing to recurse on
                    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 we found something with index=None, recurse
                    if pi < len(v.adj):
                        w = v.adj[pi]
                        call_stack.append((v,pi+1))
                        call_stack.append((w,0))
                        continue
                    # If v is the root of a connected component
                    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

    #print(scc3(vs))
    #print(scc2(vs))
    #print(scc(vs))
    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()


#same code but with using bootstrap recursion


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:
    # initialize graph
    def __init__(self, gdict=None):
        if gdict is None:
            gdict = defaultdict(list)
        self.gdict, self.edges, self.l = gdict, [], defaultdict(int)

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

    @bootstrap
    def scc_utils(self, v):

        # initilaize time and disc
        self.disc[v], self.low[v], self.stack[v] = self.time, self.time, 1
        self.time += 1
        self.st.append(v)

        # loop edges
        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])

            # print founded scc
        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)


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

class Graph(object):
	"""docstring for Graph"""
	def __init__(self,n,d): # Number of nodes and d is True if directed
		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): # NORMAL BFS
		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): # Iterative DFS
		stack=[root]
		stack2=[]
		while len(stack)!=0: # INITIAL TRAVERSAL
			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): # Iterative DFS
		stack=[root]
		stack2=[]
		cost = 10**18
		count = 0
		while len(stack)!=0: # INITIAL TRAVERSAL
			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
		# print (stack)
		# print (self.graph)
		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
			# print (vis)
		if a1==602483:
			print (count)
			print (vis)
			return

		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)

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)


MOD = int(1e9) + 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)