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
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long lld;
typedef unsigned long long llu;
typedef double lf;
typedef long double llf;
typedef pair<int,int> pii;
typedef pair<lld,lld> pll;
#define pb push_back
#define mp make_pair
#define dd second
#define ff first
#define sz size()
#define For(i,s,a) for(lld i=(lld)s;i<(lld)a;++i)

lld c[40];

int32_t main(void){
	int a,b;
	int d,e;
	scanf("%d%d%d%d", &a,&b,&d,&e);
	For(i,0,b){
		int g,h;
		char z;
		scanf("%d -%c %d",&g,&z,&h);
		if(z=='-')
		c[g]|=(1ll<<h),
		c[h]|=(1ll<<g);
		else
		c[g]|=(1ll<<h);
	}
	//For(hh,0,20)
	For(i,1,a+1)
	For(j,1,a+1)
	For(k,1,a+1){
		if(c[i] & (1ll<<j))
		c[i]|=c[j];
		if(c[j] & (1ll<<k))
		c[j]|=c[k];
		if(c[k] & (1ll<<i))
		c[k]|=c[i];
	}
	int E = 1<<e;
	lld wyn = 0;
	For(x,1,E){
		int ok = 1;
		For(i,1,d+1)if(!(c[i] & ((lld)x<<(lld)d)))
		{ok=0;break;}
		wyn += ok;
	}
	printf("%lld",wyn);
}

/*
6 8 3 3
2 -> 1
2 -> 3
1 -> 3
3 -- 6
1 -> 4
2 -> 5
4 -> 6
4 -- 5
*/