1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

typedef struct{int p; int q;} edge;

int asc(const void *a, const void *b)
{
  int p = ((edge *)a)->p - ((edge *)b)->p;
  int q = ((edge *)a)->q - ((edge *)b)->q;
  return p+q*(p==0);
}

edge e[800000];
int f[200001];
int o[200000];
int s[200000];
short c[200000];
short v[200000];
const int d = 1e9+7;

int inv(int a)
{
  long r = 1, b = a;
  for (int n = d-2; n>0; n /= 2)
  {
    if (n%2) r = (r*b)%d;
    b = b*b%d;
  }
  return r;
}

int main()
{
  int n, m, u, p, q, x[2], y;
  long r=1;
  scanf("%i%i", &n, &m);
  f[n] = m*2;
  for (int j = 0; j<n; j++) scanf("%hi", &c[j]), f[j] = -1;
  for (int i = 0; i<f[n]; i+=2)
  {
    scanf("%i%i", &p, &q);
    e[i].p = --p, e[i].q = --q;
    e[i+1].p = q, e[i+1].q = p;
  }
  qsort(e, f[n], sizeof(*e), asc);
  for (int i = f[n]-1; i>=0; i--) f[e[i].p] = i;
  for (int j = n-1, i = f[n]; j>=0; j--)
  {
    if (f[j]==-1) f[j] = i;
    else          i = f[j];
  }
  for (int j = 0; j<n; j++) if (!v[j])
  {
    x[0] = 0, x[1] = 0;
    y = 0;
    p = 0;
    q = 0;
    u = 0;
    v[j] = 2+p;
    x[p]++, y += (1-2*p)*c[j];
    s[u++] = j;
    while (u)
    {
      int w = s[--u];
      p = 1-(v[w]-2);
      for (int i = f[w]; i < f[w+1]; i++)
      {
        if (!v[e[i].q])
        {
          v[e[i].q] = 2+p;
          x[p]++, y += (1-2*p)*c[e[i].q];
          s[u++] = e[i].q;
        }
        else if (v[e[i].q] != 2+p) q = 1;
      }
    }
    if (q)
    {
      for (int i = 0; i<x[0]+x[1]-1; i++) r *= 2, r %= d;
    }
    else
    {
      long u = 0;
      long p = 1;
      long q = 1;
      for (int i = min(0, y), j = i-y; i<=x[0] && j<=x[1]; i++, j++)
      {
        if (i>0) p *= (x[0]-i+1), p %= d, p *= inv(i), p %= d;
        if (j>0) q *= (x[1]-j+1), q %= d, q *= inv(j), q %= d;
        if (i>=0 && j>=0) u += p*q%d, u %= d;
      }
      r *= u %= d;
    }
  }
  printf("%li\n", r);
  return 0;
}