Burning Couples

HXY has joined the FFF team, and now she is about to embark on her unique mission: burning couples. There are n cinemas, each hosting a couple and each containing gasoline that requires a certain fee to use. There are m directed channels connecting adjacent cinemas.

HXY possesses a special skill: if she can start at a cinema and eventually return to it by following the directed edges (a cycle), she can burn all the couples visited along that cycle with a cost equal only to the gasoline fee of the starting cinema. Note that each couple is burned exactly once (even though a cinema may be revisited) and the directed channels (roads) may be traversed repeatedly.

Since HXY can begin her cycle from any cinema, the entire set of n cinemas can always be burned, even if the underlying graph is not connected. In effect, the problem reduces to partitioning the cinemas into cycles (each cycle corresponds to a strongly connected component of the graph) such that for each cycle, HXY pays the gasoline fee of the chosen starting cinema.

Your task is to find the minimum total cost needed to burn all couples and the number of ways to achieve this minimum cost. Specifically, for each strongly connected component (SCC), you should choose a cinema with the minimum gasoline fee as the starting point. If an SCC contains multiple cinemas with the same minimum fee, any one of them is a valid choice. The minimum total cost is the sum of the minimum fees over all SCCs, and the total number of ways is the product of the counts of these minimal-fee cinemas in each SCC, taken modulo \(10^9+7\).

Input and Output Formats are described below.

inputFormat

The input consists of:

1. An integer n (\(1 \le n \le 10^5\)) representing the number of cinemas.
2. A line with n integers, where the \(i\)-th integer represents the gasoline fee at cinema \(i\) (\(1 \le cost_i \le 10^9\)).
3. An integer m (\(0 \le m \le 10^5\)) representing the number of directed channels.
4. m lines follow, each containing two integers u and v (\(1 \le u,v \le n\)), indicating a directed channel from cinema u to cinema v.

outputFormat

Output two space-separated integers: the minimum total cost to burn all couples and the number of ways to achieve that cost modulo \(10^9+7\).

sample

5
1 2 3 4 5
5
1 2
2 3
3 1
3 4
4 5

10 1