Problem Description

As is well known, HXY has joined the FFF group. Now she is about to start her delightful (and crazy) task of burning couples.

There are $n$ movie theaters, with $n$ pairs of couples each in a theater. Each theater has gasoline, but using it incurs a certain cost. There are $m$ one-way paths connecting adjacent theaters where the couples are located.

HXY has a special skill: if she can start from a point and burn the couples along a loop back to the starting point, the cost for burning the couples on this loop is only the gasoline fee of the starting point. Each pair of couples needs to be burned only once, and theaters can be visited repeatedly. She wants to spend the least amount of money to burn all the couples.

Question: What is the minimum cost required, and how many ways are there to achieve this minimum cost? Since the number of ways might be very large, output the number of ways modulo $10^9+7$.

(Note: HXY can start her loop from any point. That is, after completing one loop, she can choose any starting position for the next loop. Therefore, there is no situation where she cannot burn all the couples, even if the graph is not connected. HXY can choose vertices for her burning actions. Also, paths can be traversed repeatedly.)

Input Format

The first line contains a positive integer $n$.
The second line contains $n$ positive integers, representing the gasoline fee $w_i$ for each point.
The third line contains a positive integer $m$.
The next $m$ lines each contain two positive integers $x_i, y_i$, indicating a one-way path from $x_i$ to $y_i$.

Output Format

Output one line with two integers, representing the minimum cost and the number of ways to achieve this minimum cost.

Sample Input and Output

Sample Input #1

3
1 2 3
3
1 2
2 3
3 2

Sample Output #1

3 1

Sample Input #2

3
10 20 10
4
1 2
1 3
3 1
2 1

Sample Output #2

10 2

Notes

For $30\%$ of the data, $1 \le n, m \le 20$;
For another $10\%$ of the data, there are no loops;
For $100\%$ of the data, $1 \le n \le 10^5$, $1 \le m \le 3 \times 10^5$, $0 \le w_i \le 10^9$.

见题面 Input 部分

见题面 Output 部分