Bảo vệ security

Một thành phố có \(N\) địa điểm chiến lược và \(M\) con đường một chiều giữa các địa điểm. Là thị trưởng của thành phố, bạn sẽ phải bảo vệ an toàn cho \(N\) địa điểm này.

Để có thể bảo vệ cho các địa điểm, bạn phải xây dựng các đồn cảnh sát tại một vài địa điểm. Đồn cảnh sát tại địa điểm \(i\) có thể bảo vệ cho địa điểm \(j\) nếu \(i = j\) hoặc cảnh sát có thể đi tuần tới địa điểm \(j\) từ \(i\) và có thể quay trở lại đồn tại địa điểm \(i\).

Để có thể xây dựng được các đồn cảnh sát cần phải mất chi phí, do địa hình mỗi địa điểm là khác nhau nên chi phí xây dựng đồn cũng có thể khác nhau.

Bạn phải xác định số tiền nhỏ nhất để xây dựng các đồn cảnh sát để có thể bảo vệ được tất cả \(N\) địa điểm, hơn nữa bạn phải đưa ra có bao nhiêu cách xây dựng để đảm bảo chi phí nhỏ nhất đó.

Input

• Dòng \(1\) chứa số nguyên dương \(N\) \((1 \leq N \leq 10^5)\)

• Dòng \(2\) chứa \(N\) số nguyên, trong đó số nguyên thứ \(i\) là chi phí để xây dựng đồn cảnh sát tại địa điểm \(i\) (chi phí $ \leq 10^9$).

• Dòng \(3\) chứa số nguyên \(M\) \((0 \leq M \leq 3 \times 10^5)\)

• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u\) và \(v\) \((1 \leq u, v \leq n; u \neq v)\) biểu diễn một con đường một chiều nối từ địa điểm \(u\) tới \(v\). Không có nhiều hơn \(1\) con đường nối giữa \(2\) địa điểm.

Output

Một dòng duy nhất chứa hai số, số thứ nhất là chi phí nhỏ nhất để xây dựng các đồn cảnh sát, số thứ hai là số phương án xây dựng mod \(10^9+7\).

Example

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

8 2