In the Isle of Guernsey there are n different types of coins. For each i (1 ≤ i ≤ n), coin of type i is worth ai cents. It is possible that ai = aj 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 bi, ci tells Jessie that Bessie has a strictly greater number of coins of type bi than coins of type ci. It is known that all bi are distinct and all ci 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 (109 + 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 ≤ 105). The second line contains n space separated integers, a1, a2, ..., an (1 ≤ ai ≤ 105). The next q lines each contain two distinct space-separated integers, bi and ci (1 ≤ bi, ci ≤ n; bi ≠ ci).

It's guaranteed that all bi are distinct and all ci are distinct.

Output

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

Examples

Input

4 2 17
3 1 2 5
4 2
3 4


Output

3


Input

3 2 6
3 1 1
1 2
2 3


Output

0


Input

3 2 10
1 2 3
1 2
2 1


Output

0

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 bi and ci,  the problem conditions are still satisfied because all bi are distinct and all ci are distinct.
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.util.ArrayList;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Collection;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Diego Huerfano ( diego.link )
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		OutputWriter out = new OutputWriter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n=in.readInt(), q=in.readInt(), t=in.readInt();
        int a[]=in.readInts( n );
        ArrayList<Integer>graph[]=new ArrayList[n];
        boolean visited[]=new boolean[n];
        boolean start[]=new boolean[n];
        Arrays.fill( start, true );
        for( int i=0; i<n; i++ )
            graph[i]=new ArrayList<Integer>();
        int ai, bi;
        for( int i=0; i<q; i++ ) {
            ai=in.readInt()-1;
            bi=in.readInt()-1;
            graph[ai].add( bi );
            start[bi]=false;
        }
        for( int i=0; i<n; i++ ) if( start[i] ) {
            visited[i]=true;
            if( graph[i].isEmpty() ) continue;
            Queue<Integer>Q=new LinkedList<Integer>();
            Q.offer( i );
            t-=a[i];
            if( t<0 ) {
                out.printLine( 0 );
                return;
            }
            while( !Q.isEmpty() ) {
                int u=Q.poll();
                int v=graph[u].get( 0 );
                visited[v]=true;
                a[v]+=a[u];
                if( !graph[v].isEmpty() ) {
                    t-=a[v];
                    if( t<0 ) {
                        out.printLine( 0 );
                        return;
                    }
                    Q.offer( v );
                }
            }
        }
        for( boolean value : visited ) {
            if( !value ) {
                out.printLine( 0 );
                return;
            }
        }
        final int MODULO=(int)1e9+7;
        int dp[]=new int[t+1];
        dp[0]=1;
        for( int j : a ) {
            for( int i=j; i<=t; i++ ) {
                dp[i]+=dp[i-j];
                dp[i]%=MODULO;
            }
        }
        out.printLine( dp[t] );
    }
}

class InputReader {

    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    public int readInt() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public int[] readInts( int n ){
        int ans[]=new int[n];
        for( int i=0; i<n; i++ ) ans[i]=readInt();
        return ans;
    }

    public boolean isSpaceChar(int c) {
        if (filter != null)
            return filter.isSpaceChar(c);
        return isWhitespace(c);
    }

    public static boolean isWhitespace(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public interface SpaceCharFilter {
        public boolean isSpaceChar(int ch);
    }
}

class OutputWriter {
    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public OutputWriter(Writer writer) {
        this.writer = new PrintWriter(writer);
    }

    public void print(Object...objects) {
        for (int i = 0; i < objects.length; i++) {
            if (i != 0)
                writer.print(' ');
            writer.print(objects[i]);
        }
    }

    public void printLine(Object...objects) {
        print( objects );
        writer.println();
    }

    public void close() {
        writer.close();
    }
}

