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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef set<int> SI;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;

const int INF = 1000000001;
const LD EPS = 1e-9;
const int MOD = 1000000007;
const LL LLINF = 1000000000000000001;

#define FOR(i, b, e) for(int i = b; i <= e; i++)
#define FORD(i, b, e) for(int i = b; i >= e; i--)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(x) ((int)(x).size())
#define DPRINT(x) cout << #x << ": " << x << endl
#define BOOST ios_base::sync_with_stdio(false); cin.tie(0)

#define MP make_pair
#define PB push_back
#define ST first
#define ND second
#define GGL(x) "Case #" << x << ": "

// ゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴ




const int maxn = 500042;
VI gr[maxn];

bool seen[maxn];
void dfs(int a)
{
    seen[a] = true;
    for(auto i : gr[a])
        if(!seen[i])
            dfs(i);
}

LL reach[maxn];

int main()
{
    BOOST;

    int n, m, a, b;
    cin >> n >> m >> a >> b;

    FOR(i, 1, m)
    {
        int a, b;
        char c;
        cin >> a >> c;
        cin >> c >> b;
        gr[b].PB(a);
        if(c == '-')
            gr[a].PB(b);
    }

    FOR(i, 0, b-1)
    {
        FOR(i, 1, n)
            seen[i] = false;
        dfs(a+i+1);
        FOR(j, 0, a-1)
            if(seen[j+1])
                reach[i] += (1 << j);
    }

    int ans = 0;
    FOR(mask, 0, (1<<b)-1)
    {
        int r = 0;
        FOR(j, 0, b-1)
            if(mask & (1<<j))
                r |= reach[j];
        if(r == (1<<a)-1)
            ans++;
    }

    cout << ans << '\n';
            


}