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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#include <bits/stdc++.h>
using namespace std;
const int MX=500050,md=1000000007;
int tot,res,dpn,n,m,a,b,x,y,i,j,cc,c[MX],cnta[MX],cntb[MX],out[MX],all[MX],le[MX],ri[MX],lft[MX],pos[MX],fin[MX],finsz,fi,fr,q[MX];
vector<int> g[MX],o[MX],vg[MX],vo[MX];
long long pw2[MX],f[MX],oth;
bool u[MX],w[MX],was;
pair<int,int> e[MX];
vector<pair<int,int>> otr[MX];
char st[7];
void dfs(int i) {
  u[i]=true;
  for (int j=0; j<g[i].size(); j++) if (!u[g[i][j]]) dfs(g[i][j]);
  all[++tot]=i;
}
void ofs(int i) {
  c[i]=cc;
  //printf("c %d <- %d\n",i,cc);
  if (i<=a) cnta[cc]++; else if (i<=a+b) cntb[cc]++;
  for (int j=0; j<o[i].size(); j++) if (c[o[i][j]]==0) ofs(o[i][j]);
}
void cutfront(int i) {
  u[i]=false;
  for (int j=0; j<vo[i].size(); j++) if (u[vo[i][j]]) cutfront(vo[i][j]);
}
void vfs(int i) {
  w[i]=true;
  for (int j=0; j<vg[i].size(); j++) if (!w[vg[i][j]]) vfs(vg[i][j]);
}
void upd(int i, int x) {
  otr[i].emplace_back(x,x);
}
void upd_intersect(int i, int l, int r) {
  otr[i].emplace_back(l,r);
/*  if (le[i]==0) {
    le[i]=l;
    ri[i]=r;
    return;
  }
  //printf("%d: [%d %d] upd with [%d %d]",i,le[i],ri[i],l,r);
  if (le[i]<ri[i]) le[i]+=tot;
  if (l<r) l+=tot;
  if (l<le[i] && r>=le[i]-1) {
    le[i]=l;
    ri[i]=max(ri[i],r);
  } else if (r>ri[i] && l<=ri[i]+1) {
    ri[i]=r;
    le[i]=min(le[i],l);
  } else if (le[i]<l && ri[i]>=l-1) {
    ri[i]=max(ri[i],r);
  } else if (ri[i]>r && le[i]<=r+1) {
    le[i]=min(le[i],l);
  } else if (r==tot && le[i]==1) {
    le[i]=l;
    ri[i]+=tot;
  } else if (ri[i]==tot && l==1) {
    ri[i]=tot+r;
  }
  if (ri[i]-le[i]+1>=tot) { le[i]=1; ri[i]=tot; }
  if (ri[i]>tot) ri[i]-=tot;
  //printf(" ====> [%d %d]\n",le[i],ri[i]);*/
}
int main() {
  scanf("%d%d%d%d",&n,&m,&a,&b);
  for (pw2[0]=i=1; i<=n; i++) pw2[i]=(pw2[i-1]*2LL)%md;
  for (i=0; i<m; i++) {
    scanf("%d",&x);
    scanf("%s",st);
    scanf("%d",&y);
    g[x].push_back(y);
    o[y].push_back(x);
    if (st[1]=='-') {
      g[y].push_back(x);
      o[x].push_back(y);
    }
  }
  for (i=1; i<=n; i++) if (!u[i]) dfs(i);
  for (i=tot; i>0; i--) if (c[all[i]]==0) {
    ++cc;
    ofs(all[i]);
  }
  for (i=1; i<=n; i++) for (j=0; j<g[i].size(); j++) {
    x=g[i][j];
    if (c[i]!=c[x]) {
      vg[c[i]].push_back(c[x]);
      vo[c[x]].push_back(c[i]);
    }
  }
  for (i=1; i<=cc; i++) if (u[i] && cnta[i]>0)
    for (j=0; j<vo[i].size(); j++) if (u[vo[i][j]]) cutfront(vo[i][j]);
  for (i=1; i<=cc; i++) if (u[i] && !w[i] && cnta[i]>0) vfs(i);
  for (i=1; i<=cc; i++) if (w[i]) {
    for (j=0; j<vg[i].size(); j++) if (w[vg[i][j]]) out[i]++;
    if (out[i]==0) q[fr++]=i;
  }
  for (tot=0, i=a+1; i<=a+b; i++) if (w[c[i]]) {
    ++tot;
    //printf("%d -> %d (%d)\n",i,c[i],tot);
    upd(c[i],tot);
  }
  oth=b-tot;
  for (fi=0; fi<fr; fi++) {
    x=q[fi];
    if (!otr[x].empty()) {
      //printf("component %d: [%d %d]\n",x,le[x],ri[x]);
      sort(otr[x].begin(),otr[x].end());
      int rgh=otr[x][0].second;
      for (j=1; j<otr[x].size(); j++) {
        if (otr[x][j].first>rgh+1) break;
        rgh=otr[x][j].second;
      }
      if (j==otr[x].size()) {
        le[x]=otr[x][0].first;
        ri[x]=otr[x].back().second;
      } else {
        le[x]=otr[x][j].first;
        ri[x]=otr[x][j-1].second;
      }
      //for (j=0; j<otr[x].size(); j++) printf("[%d %d],",otr[x][j].first,otr[x][j].second);
      //printf("~ component %d: [%d %d]\n",x,le[x],ri[x]);
      for (j=0; j<vo[x].size(); j++) {
        y=vo[x][j];
        if (w[y]) {
          upd_intersect(y,le[x],ri[x]);
          if (--out[y]==0) q[fr++]=y;
        }
      }
    }
  }
  int lftz=n=0;
  for (i=1; i<=cc; i++) if (w[i] && cnta[i]>0) {
    if (le[i]==0 || ri[i]==0) { puts("0"); return 0; }
    if (le[i]!=1 || ri[i]!=tot) lftz=(lftz==0)?le[i]:min(lftz,le[i]);
  }
  if (lftz==0) { printf("%d\n",int((((pw2[tot]+md-1)%md)*pw2[oth])%md)); return 0; }
  for (i=1; i<=cc; i++) if (w[i] && cnta[i]>0) {
    le[i]-=lftz; if (le[i]<=0) le[i]+=tot;
    ri[i]-=lftz; if (ri[i]<=0) ri[i]+=tot;
    if (ri[i]+1==le[i]) { le[i]=1; ri[i]=tot; }
    e[n++]={ri[i],i};
    //printf("seg [%d %d]\n",le[i],ri[i]);
  }
  sort(e,e+n);
  for (i=0; i<n; i=j) {
    lft[++dpn]=le[e[i].second];
    for (j=i; j<n && e[i].first==e[j].first; j++) {
      y=le[e[j].second];
      if (y<=e[j].first) {
        if (lft[dpn]>e[j].first || lft[dpn]<y) lft[dpn]=y;
      } else if (lft[dpn]>e[j].first && lft[dpn]<y) lft[dpn]=y;
    }
    pos[dpn]=e[i].first;
    //printf("lft=%d pos=%d\n",lft[dpn],pos[dpn]);
    if (lft[dpn]>e[i].first || !was) {
      for (x=0; x<finsz; x++) if (lft[fin[x]]==lft[dpn]) break;
      if (x>=finsz) {
        if (lft[dpn]<=e[i].first) was=true;
        fin[finsz++]=dpn;
        //printf("  in fin\n");
      }
    }
  }
  int lst=0;
  for (i=1; i<=dpn; i++) {
    if (lft[i]<=pos[i] && lft[i]>lst) oth=(oth+lft[i]-lst-1)%md;
    lst=pos[i];
  }
  for (x=0; x<finsz; x++) {
    for (i=0; i<fin[x]; i++) f[i]=0;
    if (x==0) f[i]=(pw2[pos[i]]+md-1)%md; else f[i]=(pw2[pos[i]-pos[fin[x-1]]]+md-1)%md;
    //printf("# %d %d = %d\n",x,i,int(f[i]));
    int wh=-1;
    for (++i; i<=dpn; ++i) {
      if (x+1<finsz && wh==-1 && pos[i]>=lft[fin[x]]) wh=i;
      f[i]=0;
      lftz=lft[i-1];
      if (lftz>pos[i-1]) lftz=0;
      for (j=i-1; j>=0 && pos[j]>=lftz; j--) {
        f[i]=(f[i]+f[j])%md;
        //printf(" %d <- %d (%d)\n",i,j,int(f[j]));
      }
      int cle=pos[i-1];
      if (lft[i]<=pos[i] && lft[i]-1>cle) cle=lft[i]-1;
      f[i]=(f[i]*(pw2[pos[i]-cle]+md-1LL))%md;
      //printf("%d %d = %d\n",x,i,int(f[i]));
    }
    if (x+1==finsz) {
      for (j=dpn; j>=0 && pos[j]>=lft[fin[x-1]]; j--) res=(res+f[j])%md;
    } else {
      if (wh==-1) j=dpn; else for (j=dpn; j>=wh; j--) res=(res+f[j])%md;
      res=(res+f[j]*(pw2[tot-lft[fin[x]]+1]+md-1))%md;
    }
    //printf("res=%d\n",int((res)%md));
  }
  printf("%d\n",int((res*pw2[oth])%md));
  return 0;
}