Port Selection on Bit Island

Bit Island is located in the sea with an inland lake at its center. There are (n) points numbered from (1) to (n) on the island. Points (1) to (a) represent the boundary of the inland lake (listed in either clockwise or counterclockwise order), points (a+1) to (a+b) represent the coastline, and the remaining points are neither on the lake side nor on the sea side.

These points are connected by (m) roads. Each road is either one-way or two-way, does not pass through the lake, sea, or any other points, and there is at most one road between any pair of points. The roads are drawn in a plane without overpasses or tunnels (i.e. any two roads can only intersect at their endpoints). Moreover, from every lake-side point (points (1,2,\dots,a)), it is possible to reach at least one sea-side point (points (a+1, a+2,\dots,a+b)) directly or indirectly.

Your task is to choose a subset of the (b) sea-side points as ports such that every lake-side point can reach at least one port. Determine the number of ways to choose such a subset.

inputFormat

The first line contains four integers (n, m, a, b).

Each of the next (m) lines contains three integers (u, v, d) describing a road between points (u) and (v). If (d = 1), the road is directed from (u) to (v); if (d = 0), the road is bidirectional.

outputFormat

Output a single integer: the number of valid selections of sea-side points such that every lake-side point can reach at least one chosen port.

sample

5 5 1 1
1 2 1
2 3 0
3 4 1
4 5 0
5 1 1

1