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*<sub class="lower-index">*i*</sub> cents. It is possible that *a*<sub class="lower-index">*i*</sub> = *a*<sub class="lower-index">*j*</sub> 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*<sub class="lower-index">*i*</sub>, *c*<sub class="lower-index">*i*</sub> tells Jessie that Bessie has a strictly greater number of coins of type *b*<sub class="lower-index">*i*</sub> than coins of type *c*<sub class="lower-index">*i*</sub>. It is known that all *b*<sub class="lower-index">*i*</sub> are distinct and all *c*<sub class="lower-index">*i*</sub> 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<sup class="upper-index">9</sup> + 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<sup class="upper-index">5</sup>). The second line contains *n* space separated integers, *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">5</sup>). The next *q* lines each contain two distinct space-separated integers, *b*<sub class="lower-index">*i*</sub> and *c*<sub class="lower-index">*i*</sub> (1 ≤ *b*<sub class="lower-index">*i*</sub>, *c*<sub class="lower-index">*i*</sub> ≤ *n*; *b*<sub class="lower-index">*i*</sub> ≠ *c*<sub class="lower-index">*i*</sub>).

It's guaranteed that all *b*<sub class="lower-index">*i*</sub> are distinct and all *c*<sub class="lower-index">*i*</sub> are distinct.
//#include<bits/stdc++.h>
#include <iostream>
#include <stdio.h>
#define P7 1000000007

using namespace std;

int a[305],g[305][305],h[305],f[305];
long long DP[100020];
int n,q,t,x,y,i,j,z[305];

void go(int p,int u,int tmp)
 {
  if (f[u]) { cout<<0<<endl; exit(0); }
  int ans=0;
  for (int i=1;i<=n;i++)
   if (i != u && i != p && g[u][i])
    {
     go(u,i,tmp+a[u]);
     h[u]=max(h[u],h[i]+1);
     ans+=a[i];
    }
  t-=h[u]*a[u];
  a[u]+=tmp;
  cout<<h[u]<<" "<<a[u]<<endl;
  if (t < 0) { cout<<0<<endl; exit(0); }
 }
main()
 {
  cin>>n>>q>>t;
  for (i=1;i<=n;i++)
   cin>>a[i];
  for (i=1;i<=q;i++)
   {
    cin>>x>>y;
    if (g[y][x]) { cout<<0<<endl; return 0; }
    g[x][y]=1;
    z[y]++;
   }
  for (i=1;i<=n;i++)
   if (!z[i]) go(0,i,0);
  DP[0]=1;
  sort(a+1,a+n+1);
   for (j=1;j<=n;j++)
    for (i=a[j];i<=t;i++)
     DP[i]=(DP[i]+DP[i-a[j]])%P7;
  cout<<DP[t]<<endl; cin>>n;
 }
