#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define all(a) (a).begin(),(a).end()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector< pair<vi,vi> > TD;
const ll mod = 1e9+7;

inline vector<vi> construct_graph(int n){
  vi l(n), sum(n+1,0);
  rep(i,n){
    cin >> l[i];
    sum[i+1] = sum[i] + 2*l[i]+6;
  }

  vi same(sum[n]);
  rep(i,sum[n])same[i] = i;
  rep(i,n-1){
    int f,p,t,q;
    cin >> f >> p >> t >> q;
    same[sum[t]+2*q+2] = sum[f]+2*p+2; same[sum[t]+2*q+4] = sum[f]+2*p+3;
    same[sum[t]+2*q+3] = sum[f]+2*p+4; same[sum[t]+2*q+5] = sum[f]+2*p+5;
  }
  
  vi id;
  rep(i,sum[n])id.push_back(same[i]);
  sort(all(id));
  id.erase(unique(all(id)),id.end());

  vector<vi> graph(id.size());
  rep(i,n){
    rep(j,2*l[i]+4){
      int id1 = sum[i] + j, id2 = id1 + 2;
      id1 = lower_bound(all(id),same[id1]) - id.begin();
      id2 = lower_bound(all(id),same[id2]) - id.begin();
      graph[id1].push_back(id2);
      graph[id2].push_back(id1);
    }
    rep(j,l[i]+1){
      int id1 = sum[i] + 2*(j+1) , id2 = id1 + 1;
      id1 = lower_bound(all(id),same[id1]) - id.begin();
      id2 = lower_bound(all(id),same[id2]) - id.begin();
      graph[id1].push_back(id2);
      graph[id2].push_back(id1);
    }
  }

  rep(i,id.size()){
    sort(all(graph[i]));
    graph[i].erase(unique(all(graph[i])),graph[i].end());
  }

  vector<vi> res(id.size(), vi(id.size(),0));
  rep(i,id.size()){
    for(int u : graph[i])res[i][u] = 1;
  }
  return res;
}

/*Tree Decomposition for a graph with small treewidth.*/
inline TD heuristic_tree_decomposition(vector<vi> g){
  int n = g.size();
  TD res = TD(n);
  vi use(n,-1), deg(n);
  rep(i,n)deg[i] = accumulate(all(g[i]),0);

  int id = n-1;
  for(;;){
    int v = -1;
    rep(i,n){
      if(use[i]==-1 && (v<0 || deg[i] < deg[v]))v = i;
    }
    if(v<0)break;

    vi unuse;
    rep(u,n){
      if(g[v][u]==1){
	if(use[u]==-1)unuse.push_back(u);
	else if(use[u]>=0){
	  res[id].first.push_back(use[u]);
	  use[u] = -2;
	}
	deg[u]--;
      }
    }

    res[id].second.push_back(v);
    for(int a : unuse){
      res[id].second.push_back(a);
      for(int b :unuse){
	if(a!=b && g[a][b]==0){
	  g[a][b] = 1; deg[a]++; 
	}
      }
    }

    use[v] = id;
    id--;
  }

  return res;
}

inline void toNice(TD &t, const int &id){
  //for join
  while(t[id].first.size()>2){
    vi child(2);
    child[0] = t[id].first.back(); t[id].first.pop_back();
    child[1] = t[id].first.back(); t[id].first.pop_back();
    t.push_back(make_pair(child, t[id].second));
    t[id].first.push_back(t.size()-1);
  }

  if(t[id].first.size()==2){
    rep(i,2){
      const int &j = t[id].first[i];
      if(t[id].second != t[j].second){
	vi child(1);
	child[0] = j;
	t.push_back(make_pair(child, t[id].second));
	t[id].first[i] = t.size()-1;
      }
    }
  }

  //for introduce & forget
  if(t[id].first.size()==1){
    const int &j = t[id].first[0];
    vi child(1);
    child[0] = j;

    vi disA, disB;
    rep(a,t[id].second.size()){
      bool f = true;
      rep(b,t[j].second.size()){
	if(t[id].second[a] == t[j].second[b])f = false;
      }
      if(f)disA.push_back(a);
    }
    rep(b,t[j].second.size()){
      bool f = true;
      rep(a,t[id].second.size()){
	if(t[id].second[a] == t[j].second[b])f = false;
      }
      if(f)disB.push_back(b);
    }

    if(disA.size() + disB.size() > 1){
      if(disA.size()>0){
	vi tmp = t[id].second;
	tmp.erase(tmp.begin() + disA[0]);
	t.push_back(make_pair(child, tmp));
	t[id].first[0] = t.size()-1;
      }else{
	vi tmp = t[id].second;
	tmp.push_back(t[j].second[disB[0]]);
	t.push_back(make_pair(child, tmp));
	t[id].first[0] = t.size()-1;
      }      
    }
  }

  //for leaf
  if(t[id].first.size() == 0){
    if(t[id].second.size() > 1){
      vi tmp;
      rep(i,t[id].second.size()-1)tmp.push_back(t[id].second[i]);
      t.push_back(make_pair(vi(), tmp));
      t[id].first.push_back(t.size()-1);
    }
  }

  rep(i,t[id].first.size())toNice(t, t[id].first[i]);
}

vi desc;
void descendant(const TD &t, const int &id){
  for(int v : t[id].first)descendant(t,v);

  if(t[id].first.size()==0)desc[id] = 1;
  else if(t[id].first.size()==2){
    desc[id] = desc[t[id].first[0]] + desc[t[id].first[1]] - t[id].second.size();
  }else{
    const int &v = t[id].first[0];
    if(t[v].second.size() < t[id].second.size()){
      desc[id] = desc[v] + 1;
    }else{
      desc[id] = desc[v];
    }
  }
}

unordered_map<ll,ll> memo;
const int con_mat[3][3] = { {0, 1, 4}, {1, 0, 2}, {4, 2, 0} };

inline ll rec(const int &cur, const vi &col, const int &con, const vi &nums,
       const TD &ntd, const int &k, const vector<vi> &g){
  const vi& child = ntd[cur].first, bag = ntd[cur].second;
  int w = col.size();

  //check memo
  ll state = 0;
  rep(i,w)state |= (ll)col[i]<<i;
  state |= (ll)con<<3;
  rep(i,w)state |= (ll)nums[i]<<(4*i+6);
  state |= (ll)cur<<18;
  if(memo.count(state))return memo[state];

  //pruning
  int comb = w*(w-1)/2;
  vi deg(w,0);
  rep(i,comb){
    if( (con>>i)&1 ){
      deg[i]++; deg[(i+1)%w]++;
    }
  }
  rep(i,w){
    if(deg[i]+1 > nums[i])return 0;
  }

  //for leaf
  if(child.size()==0){
    if(con == 0 && nums[0] == 1)return 1;
    return 0;
  }

  ll res = 0;
  if(child.size()==1){
    const vi &nbag = ntd[child[0]].second;
    vi to_bag(nbag.size(),-1), to_nbag(bag.size(),-1);
    rep(i,bag.size())rep(j,nbag.size()){
      if(bag[i] == nbag[j]){
	to_bag[j] = i; to_nbag[i] = j;
      }
    }

    //for introduce
    if(nbag.size() < bag.size()){
      vi ncol(nbag.size()), nnums(nbag.size());
      rep(i,nbag.size()){
	ncol[i] = col[to_bag[i]];
	nnums[i] = nums[to_bag[i]];
      }

      int del = -1;
      rep(i,bag.size()){
	if(to_nbag[i]<0)del = i;
      }

      int ncon = (nbag.size()==2 && (con_mat[to_bag[0]][to_bag[1]] & con))?1:0;

      if(deg[del] == 0){
	if(nums[del] != 1)return memo[state] = 0;
	res += rec(child[0], ncol, ncon, nnums, ntd, k, g);
      }else if(deg[del] == 1){
	int a=-1,b=-1;
	rep(i,comb){
	  if((con>>i)&1)a = i, b = (i+1)%w;
	}
	if(a==del)a = b;
	if( !g[bag[del]][bag[a]] )return memo[state] = 0;
	nnums[to_nbag[a]]--;
	res += rec(child[0], ncol, ncon, nnums, ntd, k, g);
      }else{
	if( !g[bag[del]][nbag[0]] && !g[bag[del]][nbag[1]] )return memo[state] = 0;
	nnums[0]--; nnums[1]--;
	res += rec(child[0], ncol, 1, nnums, ntd, k, g);

	if( g[bag[del]][nbag[0]] && g[bag[del]][nbag[1]] ){
	  int tmp = nnums[0];
	  rep(i,tmp-1){
	    nnums[0] = i+1; nnums[1] = tmp-i-1;
	    res += rec(child[0], ncol, 0, nnums, ntd, k, g);
	  }
	}
      }
    }
    //for forget
    if(nbag.size() > bag.size()){
      vi ncol(nbag.size()), nnums(nbag.size()), tmpnums(nbag.size());
      int add = -1;

      rep(i,nbag.size()){
	if(to_bag[i]<0)  add = i;
	else{
	  ncol[i] = col[to_bag[i]];
	  nnums[i] = nums[to_bag[i]];
	}
      }
      
      int ncon = 0;
      if(bag.size()==2 && con){
	ncon = con_mat[to_nbag[0]][to_nbag[1]];
      }
      
      rep(nadd,2){
	ncol[add] = nadd;
	
	if(bag.size() == 1){
	  int b = to_nbag[0];
	  if( ncol[add] == ncol[b] ){
	    tmpnums[add] = tmpnums[b] = nnums[b];
	    res += rec(child[0], ncol, 1, tmpnums, ntd, k, g);
	  }
	  if( ncol[add] != ncol[b] || g[nbag[add]][nbag[b]] == 0){
	    tmpnums[b] = nnums[b];
	    rep(i,k){
	      tmpnums[add] = i+1;
	      res += rec(child[0], ncol, 0, tmpnums, ntd, k, g);
	    }
	  }
	}else{
	  int a = to_nbag[0], b = to_nbag[1];
	  bool con1 = (ncol[add] == ncol[a]) && (g[nbag[add]][nbag[a]] == 1);
	  bool con2 = (ncol[add] == ncol[b]) && (g[nbag[add]][nbag[b]] == 1);

	  if(con){
	    if( !con1 && !con2 ){
	      if(g[nbag[a]][nbag[b]] == 0)continue;

	      tmpnums[a] = nnums[a]; tmpnums[b] = nnums[b];
	      rep(i,k){
		if(nnums[a] + i+1 > desc[child[0]])break;
		tmpnums[add] = i+1;
		res += rec(child[0], ncol, ncon, tmpnums, ntd, k, g);
	      }
	    }
	    if( ncol[add] == ncol[a] ){
	      tmpnums[add] = tmpnums[a] = tmpnums[b] = nnums[b];
	      res += rec(child[0], ncol, 7, tmpnums, ntd, k, g);
	    }
	  }else{
	    if( ncol[add] == ncol[a] && !con2){
	      tmpnums[add] = tmpnums[a] = nnums[a];
	      tmpnums[b] = nnums[b];
	      res += rec(child[0], ncol, con_mat[add][a], tmpnums, ntd, k, g);
	    }

	    if( ncol[add] == ncol[b] && !con1){
	      tmpnums[add] = tmpnums[b] = nnums[b];
	      tmpnums[a] = nnums[a];
	      res += rec(child[0], ncol, con_mat[add][b], tmpnums, ntd, k, g);
	    }

	    if( !con1 && !con2 ){
	      tmpnums[a] = nnums[a]; tmpnums[b] = nnums[b];
	      rep(i,k){
		if(nnums[a] + nnums[b] + i+1 > desc[child[0]])break;
		tmpnums[add] = i+1;
		res += rec(child[0], ncol, ncon, tmpnums, ntd, k, g);
	      }
	    }
	  }
	}
      }
    }
  }

  //for join
  if(child.size()==2){
    vi lnums(w), rnums(w);
    rep(i,w)lnums[i] = deg[i]+1;

    for(;;){
      rep(i,w){
	rnums[i] = nums[i] - lnums[i] + deg[i]+1;
      }

      int lsum = accumulate(lnums.begin(),lnums.end(),0);
      if(con&3)lsum -= lnums[1];
      if(con&4)lsum -= lnums[2];
      if(lsum <= desc[child[0]]){
	int rsum = accumulate(rnums.begin(),rnums.end(),0);
	if(con&3)rsum -= rnums[1];
	if(con&4)rsum -= rnums[2];
	if(rsum <= desc[child[1]]){

	  if(con == 0 || con == 7){
	    ll l = rec(child[0], col, con, lnums, ntd, k, g);
	    if(l!=0){
	      (res += l * rec(child[1], col, con, rnums, ntd, k, g) ) %= mod;
	    }
	  }else{
	    int a=-1,b=-1;
	    rep(i,comb){
	      if( (con>>i)&1 )a = i, b = (i+1)%w;
	    }
	    ll l = rec(child[0], col, con, lnums, ntd, k, g);
	    ll r = rec(child[1], col, con, rnums, ntd, k, g);
	    (res += l*r) %= mod;

	    if( !g[bag[a]][bag[b]] ){
	      if(l!=0){
		int tmp = rnums[a];
		rep(i,tmp-1){
		  rnums[a] = i+1; rnums[b] = tmp-i-1;
		  (res += l * rec(child[1], col, 0, rnums, ntd, k, g) ) %= mod;
		}
		rnums[a] = rnums[b] = tmp;
	      }
	      if(r!=0){
		int tmp = lnums[a];
		rep(i,tmp-1){
		  lnums[a] = i+1; lnums[b] = tmp-i-1;
		  (res += r * rec(child[0], col, 0, lnums, ntd, k, g) ) %= mod;
		}
		lnums[a] = lnums[b] = tmp;
	      }
	    }
	  }
	}
      }

      bool f = true;
      rep(i,w){
	if(lnums[i] != nums[i])f = false;
      }
      if(f)break;

      lnums[0]++;
      int p = 0;
      while(lnums[p]>nums[p]){
	lnums[p] = deg[p]+1; p++; 
	if(p<w)lnums[p]++;
	else break;
      }
      if(con){
	if(con&1)lnums[1] = lnums[0];
	if(con&2)lnums[2] = lnums[1];
	if(con&4)lnums[2] = lnums[0];
      }
    }
  }
  return memo[state] = res % mod;
}
	
int main(){
  cin.tie(0); std::ios::sync_with_stdio(0);

  int n,k;
  while(cin >> n >> k){
    if(n==0 && k==0)break;

    vector<vi> graph = construct_graph(n);
    TD t = heuristic_tree_decomposition(graph);
    toNice(t,0);
    desc.resize(t.size(),0);
    descendant(t,0);

    ll res = 0;
    vi col(1), num(1);

    memo.clear();
    col[0] = 0;
    rep(j,k){
      num[0] = j+1;
      res += rec(0,col,0,num,t,k,graph);
    }

    (res <<= 1) %= mod;
    cout << res << endl;
  }
}

Measured memory_bytes: 138384