CF427C.Checkposts

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.

你的城市有 $n$ 个路口。路口之间共有 $m$ 条单向道路。作为该市市长，你必须确保所有路口的安全。

为保障安全，你需要建造若干警察检查站。检查站只能建在路口处。位于路口 $i$ 的检查站能够保护路口 $j$，当且仅当 $i = j$，或者警用巡逻车可以从 $i$ 出发到达 $j$，再从 $j$ 返回 $i$。

建造检查站需要花费资金。由于城市中不同区域的建设成本不同，在某些路口建造检查站的费用可能高于其他路口。

你需要确定确保所有路口安全所需的最小总费用。此外，你还需计算在达到该最小费用的前提下，所需检查站数量也最少的方案总数。若两种方案中存在某个路口，在一种方案中建有检查站、而在另一种方案中没有，则认为这两种方案不同。

In the first line, you will be given an integer n, number of junctions (1 ≤ n ≤ 105). 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 109).

The next line will contain an integer m (0 ≤ m ≤ 3·105). 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.

第一行将给出一个整数 $n$，表示路口的数量（$1 \leq n \leq 10^5$）。
第二行将给出 $n$ 个用空格分隔的整数。第 $i$ 个整数表示在第 $i$ 个路口建造检查站的成本（成本为非负整数，且不超过 $10^9$）。

接下来一行将给出一个整数 $m$（$0 \leq m \leq 3 \cdot 10^5$）。随后的 $m$ 行中，每行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$；$u_i \neq v_i$）。一对 $u_i, v_i$ 表示存在一条从 $u_i$ 指向 $v_i$ 的单向道路。同一方向上任意两个节点之间至多只有一条道路。

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 (109 + 7).

输出两个由空格分隔的整数。第一个整数是确保所有路口安全所需的最少资金；第二个整数是确保安全的方案数对 $1000000007$（即 $10^9 + 7$）取模的结果。