#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>		//UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>		//do setprecision
#include <ctime>
#include <complex>
#include <chrono>
#include<unordered_map>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)
#define ALL(u) (u).begin(),(u).end()

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

typedef pair<int, int> PII;

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;

const int MR = 5e5 + 10;
const int MOD = 1e9 + 7;
const int MS = 110;

vector<int> g[MR], rev[MR];
char s[10];

bitset<MS> FW[MS];

int goBrut(int n, int a, int b)
{
	REP(i, n)for (int j : g[i])
		FW[i][j] = 1;

	REP(k, n)REP(i, n)REP(j, n)
		FW[i][j] = (FW[i][j] || (FW[i][k] && FW[k][j]));

	// jedz bruta
	int res = 0;
	FOR(mask, 1, 1 << b)
	{
		bitset<MS> port;
		REP(i, b)
			if (mask&(1 << i))
				port[a + i] = 1;

		bool ok = 1;
		REP(i, a)
			if ((port&FW[i]) == 0)
			{
				ok = 0;
				break;
			}

		res += ok;
	}

	return res;
}

int srt[MR], cnt;

int done[MR];

void dfs(int nr, vector<int> *g)
{
	done[nr] = 1;
	for (int i : g[nr])
		if (!done[i])
			dfs(i, g);

	srt[cnt++] = nr;
}

int sccNr, scc[MR], sz[MR];
void dfs(int nr)
{
	scc[nr] = sccNr;
	for (int i : rev[nr])
		if (!scc[i])
			dfs(i);
}

int pot[MR];
bool checkSCC[MR];

vector<int> jakieSCC[MR];

int main()
{
	int n, m, a, b;
	scanf("%d%d%d%d", &n, &m, &a, &b);
	REP(i, m)
	{
		int u, v;
		scanf("%d%s%d", &u, s, &v); u--; v--;
		g[u].push_back(v);
		rev[v].push_back(u);
		if (s[1] == '-')
		{
			g[v].push_back(u);
			rev[u].push_back(v);
		}
	}

	if (b < 21 && n <= MS)
	{
		printf("%d\n", goBrut(n, a, b));
		return 0;
	}

	// jedziemy specjalny case
	pot[0] = 1;
	FORQ(i, 1, b)
		pot[i] = 2 * pot[i - 1] % MOD;

	REP(i, n)
		if (!done[i])
			dfs(i, g);

	reverse(srt, srt + n);
	REP(i, n)
		if (!scc[srt[i]])
		{
			sccNr++;
			dfs(srt[i]);
		}

	REP(i, n)
		scc[i]--;

	REP(i, n)
		sz[scc[i]]++;

	{
		// spr czy wszystkie nadmorskie nie sa w jednej SCC
		int ile = 0;
		FOR(i, a, a + b)
			if (!checkSCC[scc[i]])
			{
				ile++;
				checkSCC[scc[i]] = 1;
			}
		if (ile == 1)
		{
			printf("%d\n", (pot[b] - 1 + MOD) % MOD);
			return 0;
		}
	}

	// jedz odwrotenie do topo sort i wyznacz dojscia do skladowych nadmorskich
	FORD(i, n, 0)
	{
		// zajmuj sie skladowa
		int v = scc[srt[i]];

		// spr czy dana skladowa nie ma dojscia do wszystkich
		if (jakieSCC[v].size() > 2)
			continue;

		if (srt[i] >= a && srt[i] < a + b)
		{
			// nadmorska osada
			jakieSCC[v].push_back(v);
		}

		for (int j : g[srt[i]])
		{
			if (jakieSCC[scc[j]].size() > 2)
				// mamy dojscie do wszystkich
			{
				jakieSCC[v] = jakieSCC[scc[j]];
				break;
			}
			else if (scc[j] != v)
			{
				for (int s : jakieSCC[scc[j]])
					jakieSCC[v].push_back(s);

				sort(jakieSCC[v].begin(), jakieSCC[v].end());
				jakieSCC[v].resize(unique(jakieSCC[v].begin(), jakieSCC[v].end()) - jakieSCC[v].begin());

				if (jakieSCC[v].size() > 2)
					break;
			}
		}

		sort(jakieSCC[v].begin(), jakieSCC[v].end());
		jakieSCC[v].resize(unique(jakieSCC[v].begin(), jakieSCC[v].end()) - jakieSCC[v].begin());
	}

	vector<int> alternate, mustHave;
	// jedz odwrotenie do topo sort i wyznacz konieczne badz naprzemienne osady
	FORD(i, n, 0)
		if (srt[i] < a)
		{
			// osada nad jeziorem
			int v = scc[srt[i]];

			// spr czy ma dojscie do wszystkich
			if (jakieSCC[v].size() > 2)
				continue;
			if (jakieSCC[v].size() == 2)
			{
				alternate = jakieSCC[v];
				continue;
			}

			mustHave.push_back(jakieSCC[v].front());
			sort(mustHave.begin(), mustHave.end());
			mustHave.resize(unique(mustHave.begin(), mustHave.end()) - mustHave.begin());
		}

	if (!mustHave.empty())
	{
		if (mustHave.size() == 1)
		{
			// tylko jedna skladowa obowiazkowa
			// z tej skladowej kazdy zbior, tylko nie pusty jest ok
			int res = (pot[sz[mustHave.front()]] - 1 + MOD) % MOD;
			// reszta dowolona
			res = res * (LL)pot[b - sz[mustHave.front()]] % MOD;

			printf("%d\n", res);
			return 0;
		}

		// mamy 2 obowiazkowe skladowe
		// z tych skladowych kazdy zbior, tylko nie pusty (z kazdej skladowej) jest ok
		int res = (pot[sz[mustHave.front()]] - 1 + MOD) * (LL)(pot[sz[mustHave.back()]] - 1 + MOD) % MOD;
		// reszta dowolona
		res = res * (LL)pot[b - sz[mustHave.front()] - sz[mustHave.back()]] % MOD;

		printf("%d\n", res);
		return 0;
	}

	// nie ma nic obowiazkowego, zobacz, czy jest jakas alternatywa
	if (!alternate.empty())
	{
		// z tych skladowych kazdy zbior, tylko nie pusty (w jednej moze byc pusty - tylko 1 jest potrzebna) jest ok
		int res = ((pot[sz[alternate.front()]] * (LL)pot[sz[alternate.back()]]) % MOD - 1 + MOD) % MOD;
		// reszta dowolona
		res = res * (LL)pot[b - sz[alternate.front()] - sz[alternate.back()]] % MOD;

		printf("%d\n", res);
		return 0;
	}

	// wpp wszystko oprocz pustego jest ok
	printf("%d\n", (pot[b] - 1 + MOD) % MOD);

	return 0;
}

// FOR GNU C++ use the following pattern:
// Uncomment the code below and change your main into main2
// It does not build in MS C++
// But it does increase the stack size from 256 MB on CF and uses GNU C++

//#include <Processthreadsapi.h>
//#include <iostream>
//#include <Synchapi.h>
//#include <windows.h>
//#include <process.h>
//
//DWORD WINAPI MyThreadFunction(LPVOID lpParam) {
//    main2(nullptr);
//    return 0;
//}
//int main() {
//    auto h = CreateThread(nullptr, 1024 << 20, MyThreadFunction, nullptr, STACK_SIZE_PARAM_IS_A_RESERVATION, nullptr);
//    WaitForSingleObject(h, INFINITE);
//}