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
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;
const int MOD=1000000007;

bool testCase(const vector<vector<int>>&Graf, int a, int initMask){
	queue<int>Q;
	vector<bool>Vis(Graf.size(), false);
	for(int v=a+1;initMask;v++,initMask>>=1)
		if(initMask&1){
			Q.push(v);
			Vis[v]=true;
		}
	
	while(!Q.empty()){
		int q=Q.front();
		Q.pop();
		
		for(int nei : Graf[q])
			if(!Vis[nei]){
				Vis[nei]=true;
				Q.push(nei);
			}
	}
	
	for(int i=1;i<=a;i++)
		if(!Vis[i])
			return false;
	return true;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m, a, b;
	cin >> n >> m >> a >> b;
	
	vector<vector<int>>Graf(n+1);
	for(int i=0;i<m;i++){
		int x, y;
		string dir;
		cin >> x >> dir >> y;
		Graf[y].push_back(x);
		if(dir[1]=='-')
			Graf[x].push_back(y);
	}
	
	int wnk=0;
	for(int mask=1;mask<(1<<b);mask++)
		if(testCase(Graf, a, mask))
			wnk++;
	
	cout << wnk%MOD << "\n";
	return 0;
}