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.

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.

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