In the Isle of Guernsey there are n different types of coins. For each i (1 ≤ i ≤ n), coin of type i is worth a_i cents. It is possible that a_i = a_j for some i and j (i ≠ j).

Bessie has some set of these coins totaling t cents. She tells Jessie q pairs of integers. For each i (1 ≤ i ≤ q), the pair b_i, c_i tells Jessie that Bessie has a strictly greater number of coins of type b_i than coins of type c_i. It is known that all b_i are distinct and all c_i are distinct.

Help Jessie find the number of possible combinations of coins Bessie could have. Two combinations are considered different if there is some i (1 ≤ i ≤ n), such that the number of coins Bessie has of type i is different in the two combinations. Since the answer can be very large, output it modulo 1000000007 (10⁹ + 7).

If there are no possible combinations of coins totaling t cents that satisfy Bessie's conditions, output 0.

Input

The first line contains three space-separated integers, n, q and t (1 ≤ n ≤ 300; 0 ≤ q ≤ n; 1 ≤ t ≤ 10⁵). The second line contains n space separated integers, a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁵). The next q lines each contain two distinct space-separated integers, b_i and c_i (1 ≤ b_i, c_i ≤ n; b_i ≠ c_i).

It's guaranteed that all b_i are distinct and all c_i are distinct.

Output

A single integer, the number of valid coin combinations that Bessie could have, modulo 1000000007 (10⁹ + 7).

Note

For the first sample, the following 3 combinations give a total of 17 cents and satisfy the given conditions: {0 of type 1, 1 of type 2, 3 of type 3, 2 of type 4}, {0, 0, 6, 1}, {2, 0, 3, 1}.

No other combinations exist. Note that even though 4 occurs in both b_i and c_i, the problem conditions are still satisfied because all b_i are distinct and all c_i are distinct.

Coin Troubles

Examples