题目描述

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

为了确保安全，你必须建造一些警察检查站。一个检查站只能建在一个路口。如果有一个检查站在 $i$ 路口，保护 $j$ 的条件是：$i=j$ 或者警察巡逻车可以从 $i$ 走到 $j$，并且能回到 $i$。

建造检查站要花一些钱。由于城市的某些地区比其他地区更昂贵，在某些路口修建检查站可能比其他路口花费更多的钱。

你需要找到使所有路口安全的最低花费，以及花费与最低价格相等的方案数。

如果其中任何一个路口包含其中一个检查点而不包含在另一个路口中，则两种方式是不同的。

输入格式

第一行输入一个整数 $n$ 表示路口数。

第二行输入 $n$ 个整数 $a_{i}$ 表示每个路口建检查站的花费。

第三行输入一个整数 $m$ 表示有向道路的数量。

接下来 $m$ 行，每行两个整数 $x,y$，表示一条从 $x$ 到 $y$ 的有向道路。

输出格式

一行用空格分割的两个数，分别表示最小花费和方案数，方案数模 $10^9+7$。

3
1 2 3
3
1 2
2 3
3 2

3 1

5
2 8 0 6 0
6
1 4
1 3
2 4
3 4
4 5
5 1

8 2

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

15 6

2
7 91
2
1 2
2 1

7 1

数据范围/提示

$1 \leq n \leq 10^5,0 \leq m \leq 3 \times 10^5,0 \leq a_{i} \leq 10^9$。

$1<=u_{i},v_{i}<=n,u≠v$。

最小花费不需要取模，方案数需要取模。