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 đó.

Dữ liệu vào:

- Dòng 1 chứa số nguyên dương N (1 ≤ N ≤ 10⁵)

- 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í  ≤ 10⁹).

- Dòng 3 chứa số nguyên M (0 ≤ M ≤ 3*10⁵)

- M dòng tiếp theo, mỗi dòng chứa hai số nguyên dương u và v (1 ≤ u, v ≤ n; u ≠ 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.

Kết quả ra:

- 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⁹+7)).