삼색 신장 트리

bobo에게는 간선이 빨강, 초록, 파랑 중 하나로 칠해진 무방향 그래프 $G$가 있다. bobo는 초록 간선을 $g$개 이하, 파랑 간선을 $b$개 이하로 포함하는 $G$의 신장 트리 개수를 구하려 한다. 답은 $(10^9 + 7)$로 나눈 나머지로 구한다.

첫째 줄에 정수 네 개 $n$, $m$, $g$, $b$가 주어진다. $n$은 $G$의 정점 수, $m$은 간선 수이다 ($1 \leq n \leq 40$, $0 \leq m \leq 10^5$, $0 \leq g, b < n$).

정점은 $1, 2, \dots, n$으로 번호가 매겨져 있다.

이어지는 $m$개의 줄에는 정수 세 개 $a_i$, $b_i$, $c_i$가 주어지며, 이는 정점 $a_i$와 $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$은 $i$번째 간선이 각각 빨강, 초록, 파랑임을 뜻한다.

신장 트리의 개수를 나타내는 정수 하나를 출력한다.