Tri-color Spanning Tree

Time limit2sMemory limit1024 MB

Summary

Count spanning trees of a three-colored graph with at most g green and at most b blue edges, modulo 1e9+7, for n up to 40.

Level: Hard8 of 10
Topics: Graph, Matrix, Combinatorics
Solved: No attempts yet

Problem

bobo has an undirected graph $G$ whose edges are colored red, green, or blue. He wants to count the spanning trees of $G$ that have at most $g$ green edges and at most $b$ blue edges. Report the count modulo $(10^9 + 7)$ .

Input

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

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

Each of the next $m$ lines contains three integers $a_i$ , $b_i$ , and $c_i$ , meaning that there is 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$ ). The value $c_i = 1, 2, 3$ means the $i$ -th edge is red, green, or blue, respectively.

Output

Print a single integer, the number of spanning trees.

Examples2

Example 1
Input
```
2 3 0 0
1 2 1
1 2 2
1 2 3
```
Expected output
```
1
```

Example 2

Input

Expected output