matt

#include<cstdio>
#include<cstring>
#include<vector>
#include<map>

using namespace std;

typedef unsigned long long ull;

const int mod=1000000007;
const int maxS=550;

struct state{
  int f,w,node;
  state(int f=0,int w=0,int node=0) :
    f(f),w(w),node(node) {}
  bool operator <(const state& r)const {
    return f==r.f?(w==r.w?(node<r.node):w<r.w):f<r.f;
  }
};

vector<int> graph[15];
map<state,int> M;

ull mat[maxS][maxS],pom[maxS][maxS],m3[maxS][maxS];
int n,m,h,s,e,mf,mw,waste,cnt,k1,k2;
int f[15],w[15];

void precompute(){
  for(int i=0;i<n;++i){
    for(int f=0;f<mf;++f){
      for(int w=0;w<mw;++w){
        M[state(f,w,i)]=cnt++;
      }
    }
  }
}

void create_matrix(){
  for(int i=0;i<n;++i){
    for(int j=0;j<graph[i].size();++j){
       if(f[i]==1 && w[i]==1){
         k1=(f[graph[i][j]]==1?0:1);
         k2=(w[graph[i][j]]==1?0:1);
             mat[M[state(0,0,i)] ][M[state(k1,k2,graph[i][j])]]=1;
       }
       else if(f[i]==1){
         k1=(f[graph[i][j]]==1?0:1);
         k2=(w[graph[i][j]]==1?0:1);
            for(int w=1;w<mw;++w)
              mat[M[state(0,w,i)] ][M[state(k1,k2*(w+1),graph[i][j])]]=1;
       }
       else if(w[i]==1){
         k1=(f[graph[i][j]]==1?0:1);
         k2=(w[graph[i][j]]==1?0:1);
         for(int f=1;f<mf;++f)
              mat[M[state(f,0,i)] ][M[state(k1*(f+1),k2,graph[i][j])]]=1;
       }
       else{
         k1=(f[graph[i][j]]==1?0:1);
         k2=(w[graph[i][j]]==1?0:1);
         for(int f=1;f<mf;++f)
            for(int w=1;w<mw;++w)
              mat[M[state(f,w,i)] ][M[state(k1*(f+1),k2*(w+1),graph[i][j])]]=1;
       }
    }
  }
  for(int i=0;i<M.size();++i){ //addind bonus node and edges to calc walk <=h
    mat[cnt][cnt]=1;
    mat[i][cnt]=1;
    cnt++;
  }
}

void make_equal(ull m1[maxS][maxS],ull m2[maxS][maxS]){
  for(int i=0;i<cnt;++i)
    for(int j=0;j<cnt;++j)
      m1[i][j]=m2[i][j];
}

void multiple(ull m1[maxS][maxS],ull m2[maxS][maxS]){
  memset(m3,0,sizeof m3);

  for(int i=0;i<cnt;++i)
    for(int j=0;j<cnt;++j)
      for(int k=0;k<cnt;++k){
        m3[i][j]+=(m1[i][k]*m2[k][j]);
        m3[i][j]%=mod;
      }
  make_equal(m1,m3);
}

void potentiate(){
  bool done=false;
  make_equal(pom,mat);
  while(h){
    if(h&1){
      if(done==true) multiple(mat,pom);
      else { done=true; make_equal(mat,pom);  }
    }
    multiple(pom,pom);
    h>>=1;
  }
}

void solve(){
  potentiate();
  printf("%d",mat[M[state(0,0,s)]][M[state(0,0,e)]]);
}

int main(){
scanf("%d%d%d%d%d%d%d",&n,&m,&h,&s,&e,&mf,&mw);
s--; e--;
for(int i=0;i<n;++i)
  scanf("%d%d%d",&f[i],&w[i],&waste);
for(int i=0;i<m;++i){
  int a,b;
  scanf("%d%d",&a,&b);
  a--; b--;
  graph[a].push_back(b);
  graph[b].push_back(a);
}
precompute();
create_matrix();

solve();

return 0;
}