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^{9} + 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^{5})$. The second line contains $*n*$ space separated integers, $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$ $(1 ≤ *a*_{*i*} ≤ 10^{5})$. 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^{9} + 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.