It's peak season & demand for Blue Crystal is rapidly increasing in the market. Heisenberg & Jesse Pinkman have a lot of Blue Crystal which they have to deliver to the "Distribution Centers". There are N Distribution centers (numbered from 1,2....to N) in Albuquerque, New Mexico. These distribution centers are connected via K bidirectional roads. Cost of delivering a particular amount of Blue Crystal to ith distribution center is A[i]. Once Blue Crystal is delivered to a distribution center then cost of delivering a particular amount of Blue Crystal to any Distribution Center which is reachable from this Distribution Center is Zero. In how many ways can Heisenberg & Jesse Pinkman can deliver the Blue Crystal to all the distribution center in minimum delivery cost.

INPUT

The first line contains an integer N, the number of Distribution Centers in Albuquerque, New Mexico.

The second line contains N space-separated integers, the i-th integer representing A[i]. (1-based index)

The third line contains an integer K, denoting the number 2-way roads.

Each of the next K lines contains 2 space-separated integers i, j denoting there exist a road between Distribution Centers i and j.

OUTPUT

If the Minimum Cost to deliver the Blue Crystal to all the Distribution Centers is X, then find the number of ways in which the Blue Crystal can be delivered to all the distribution centers in a delivery cost of X. Output the answer mod 1000000007.

CONSTRAINTS

1 <= N <= 10^3

1 <= K <= 10^3

1 <= A[i] <= 10^3