시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB21151066.667%

문제

bobo has got an undirected graph $G$, whose edges are colored in red, green and blue.

He would like to count the number of spanning trees with at most $g$ green edges and $b$ blue edges modulo $(10^9 + 7)$.

입력

The first line contains $4$ integers $n, m, g, b$. $n$ and $m$ denote the number of vertices and edges of $G$, respectively ($1 \leq n \leq 40, 0 \leq m \leq 10^5, 0 \leq g, b < n$).

The vertices are conveniently numbered by $1, 2, \dots, n$.

Each of the following $m$ lines contains $3$ integers $a_i, b_i, c_i$, which denotes an edge between vertices $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq n, a_i \neq b_i, 1 \leq c_i \leq 3$). $c_i = 1, 2, 3$ denotes that the color of the $i$-th edge is red, green or blue, respectively.

출력

A single integer denotes the number of spanning trees.

예제 입력 1

2 3 0 0
1 2 1
1 2 2
1 2 3

예제 출력 1

1

예제 입력 2

3 6 1 0
1 2 1
1 2 1
2 3 1
2 3 2
3 1 2
3 1 2

예제 출력 2

10