#include #include #include #include #include #include #include using namespace std; typedef vector VI; typedef vector VVI; typedef pair PII; typedef long long LL; #define range(i,a,b) for(int i=(a); i < (b); i++) #define rep(i,n) range(i,0,n) #define P 1000000007 LL C[1001][1001]; int w[1000]; LL my_pow(LL b, LL e){ LL ret = 1, prod = b; for (LL inc = e;inc>0;inc>>=1){ if (inc&1){ret *= prod; ret %= P;} prod = prod * prod % P; } return ret; } LL calc(int i, int j){ LL ret = 0; rep(k,w[j]){ret+=(k%2?-1:1)*(C[w[j]][k]*my_pow((LL)w[j]-k,(LL)w[i])%P);ret%=P;} return ret; } int main(){ int N,M,x,y,w_min,h; LL ans = 0; VVI E; VI ::iterator it; PII tmp; map V; priority_queue > Q; C[0][0] = 1; rep(i,1000) rep(j,i+1){ C[i+1][j]+=C[i][j]; C[i+1][j]%=P; C[i+1][j+1]+=C[i][j]; C[i+1][j+1]%=P; } cin >> N >> M; E.resize(N); rep(i,N) cin >> w[i]; rep(i,M){cin >> x >> y;E[--x].push_back(--y);} rep(s,N){ V.clear(); Q.push(PII(w[s],s)); while (Q.size()>0){ tmp = Q.top(); Q.pop(); w_min = tmp.first; h = tmp.second; if (w_min <= V[h]) continue; V[h] = w_min; if(w[s] >= w[h] and w[h] <= w_min){ans += calc(s,h); ans %= P;} w_min = min(w_min,w[h]); for (it=E[h].begin(); it!=E[h].end(); it++) Q.push(PII(w_min,*it)); } } cout << ans << endl; return 0; }