bobo 拥有一个无向图 $G$，其边被染成了红色、绿色和蓝色。 他想要计算生成树的数量，要求这些生成树中绿色边的数量不超过 $g$，蓝色边的数量不超过 $b$，结果对 $(10^9 + 7)$ 取模。

输入格式

第一行包含 4 个整数 $n, m, g, b$。$n$ 和 $m$ 分别表示图 $G$ 的顶点数和边数 ($1 \le n \le 40, 0 \le m \le 10^5, 0 \le g, b < n$)。 顶点编号为 $1, 2, \dots, n$。 接下来的 $m$ 行，每行包含 3 个整数 $a_i, b_i, c_i$，表示连接顶点 $a_i$ 和 $b_i$ 的一条边 ($1 \le a_i, b_i \le n, a_i \neq b_i, 1 \le c_i \le 3$)。$c_i = 1, 2, 3$ 分别表示第 $i$ 条边的颜色为红色、绿色或蓝色。

输出格式

输出一个整数，表示满足条件的生成树数量。

样例

样例输入 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