Description

As we all know, HXY has joined the "FFF group". Now she is going to start burning couples.

There are $n$ cinemas, with $n$ couples, one couple in each cinema. Every cinema has gasoline, but using it costs a certain fee. There are $m$ directed roads connecting the cinemas of neighboring couples.

HXY has a special trick: if she can start burning from some node and eventually return to it, then the cost to burn all couples on that cycle is only the gasoline fee of that starting node. Each couple needs to be burned exactly once, while cinemas may be revisited. She wants to spend as little total cost as possible to burn all couples.

Question: what is the minimum total cost, and how many optimal ways are there to achieve this minimum? Since the number of ways may be large, output it modulo $10^9+7$.

Note: HXY can start each cycle from any node. That is, after finishing one cycle, she may choose any node as the starting point for the next cycle. Therefore, it is always possible to burn all couples; even if the graph is disconnected, HXY will choose vertices to carry out the action. Roads may be reused.

Input Format

The first line contains a positive integer $n$.
The second line contains $n$ positive integers, where $w_i$ is the gasoline fee of node $i$.
The third line contains a positive integer $m$.
Each of the next $m$ lines contains two positive integers $x_i, y_i$, indicating a directed road $x_i \to y_i$.

Output Format

Output two integers: the minimum total cost, and the number of optimal ways.

3
1 2 3
3
1 2
2 3
3 2

3 1

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

10 2

Hint

• Constraints:
  • For $30\%$ of the testdata, $1 \le n, m \le 20$.
  • For another $10\%$ of the testdata, it is guaranteed that there is no cycle.
  • For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le m \le 3 \times 10^5$, $0 \le w_i \le 10^9$.

Translated by ChatGPT 5