#include <bits/stdc++.h>
#define MAX_N 2005
#define MOD 1000000007
using namespace std;

typedef vector <int> vi;

map <int, int> dp[MAX_N];
int t, n, m, k, a, b, v[MAX_N];
int kmsk, vm[MAX_N];
bool uf[MAX_N], us[22];
vi g[MAX_N], kf;

vi factorize(int x) {
  vi dd;
  while (x % 2 == 0) {
    dd.push_back(2);
    x /= 2;
  }
  for (int i = 3; i * i <= x; i += 2)
    while (x % i == 0) {
      dd.push_back(i);
      x /= i;
    }
  if (x > 1)
    dd.push_back(x);
  return dd;
}

int calc_mask(int x) {
  vi xf = factorize(x);
  memset(us, 0, sizeof us);
  int mm = 0;
  for (int i = 0; i < (int)xf.size(); i ++)
    for (int j = 0; j < (int)kf.size(); j ++)
      if (xf[i] == kf[j] && !us[j]) {
    mm = mm | (1 << j);
    us[j] = true;
    break;
      }
  return mm;
}

int solve(int cur, int tmsk) {
  if (cur == n - 1)
    return ((tmsk == kmsk) ? 1 : 0);
  if (dp[cur].find(tmsk) == dp[cur].end()) {
    int ta = 0;
    for (int i = 0; i < (int)g[cur].size(); i ++)
      if ((tmsk | vm[g[cur][i]]) != tmsk)
    ta = (ta + solve(g[cur][i], tmsk | vm[g[cur][i]])) % MOD;
    dp[cur][tmsk] = ta;
  }
  return dp[cur][tmsk];
}

int main() {
  scanf("%d", &t);
  while (t --) {

    scanf("%d %d %d", &n, &m, &k);

    kf = factorize(k);
    kmsk = (1 << (int)kf.size()) - 1;

    for (int i = 0; i < n; i ++) {
      scanf("%d\n", &v[i]);
      uf[i] = (k % v[i]) == 0;
      g[i].clear();
      dp[i].clear();
      if (uf[i])
    vm[i] = calc_mask(v[i]);
    }

    for (int i = 0; i < m; i ++) {
      scanf("There is a door from room %d to room %d.\n", &a, &b);
      a --; b --;
      if (uf[a] && uf[b])
    g[a].push_back(b);
    }

    printf("%d\n", solve(0, vm[0]));
  }
  return 0;
}