| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 21 | 15 | 10 | 66.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.
2 3 0 0 1 2 1 1 2 2 1 2 3
1
3 6 1 0 1 2 1 1 2 1 2 3 1 2 3 2 3 1 2 3 1 2
10