There are $n$ cities in country E, numbered from $1$ to $n$. To make travel between cities more convenient, the Ministry of Transport of country E wants to build some wormholes between the $n$ cities. Each wormhole is a directed passage from one city to another. It is allowed for the start and end of a passage to be the same city, and multiple wormholes may connect two cities.

To distinguish the construction time of the wormholes, the Ministry of Transport assigns a positive integer ID to each wormhole.

We call a construction plan of wormholes "good" if it satisfies the following four conditions:

(1) There exists a non-negative integer $d$ such that every city is exactly the starting point of $d$ wormholes and exactly the ending point of $d$ wormholes. (2) For every city, among the wormholes starting from it, the IDs $1$ to $d$ each appear exactly once. (3) For every city, among the wormholes ending at it, the IDs $1$ to $d$ each appear exactly once. (4) Choose any city $u$ and positive integers $1 \le j_1, j_2 \le d$. Suppose that starting from $u$, we first traverse a wormhole with ID $j_1$, then traverse a wormhole with ID $j_2$, and arrive at city $v_1$. Suppose that starting from $u$, we first traverse a wormhole with ID $j_2$, then traverse a wormhole with ID $j_1$, and arrive at city $v_2$. Then the condition $v_1 = v_2$ must be satisfied.

In particular, a plan with no wormholes is also good.

Currently, the builders have already constructed $mn$ wormholes and assigned them IDs from $1$ to $m$. At this time, this construction plan is good. They want to build $kn$ new wormholes and assign them IDs from $(m + 1)$ to $(m + k)$. They must ensure that the construction plan formed by these $(m + k)n$ wormholes remains good. They want to know how many ways there are to build the $kn$ new wormholes such that the $(m + k)n$ wormholes form a good construction plan.

Since the answer can be very large, you only need to output the number of ways modulo $998244353$.

Input

The first line contains four non-negative integers $c, n, m, k$, where $c$ is the test case number. The $c$ in the sample indicates that the data range of the sample is the same as the data range of the $c$-th test case.

Next, there are $nm$ lines, each containing three positive integers $u, v, w$, representing a wormhole with ID $w$, starting at city $u$ and ending at city $v$.

Output

Output a single integer representing the number of ways modulo $998244353$.

Examples

Input 1

1 4 1 1
1 2 1
2 1 1
3 4 1
4 3 1

Output 1

8

Note

In this sample, the already constructed wormholes with ID $1$ are $1 \to 2, 2 \to 1, 3 \to 4, 4 \to 3$. To make the construction plan formed by $8$ wormholes good, there are $8$ possible scenarios for the newly built wormholes with ID $2$:

(1) $1 \to 1, 2 \to 2, 3 \to 3, 4 \to 4$ (2) $1 \to 1, 2 \to 2, 3 \to 4, 4 \to 3$ (3) $1 \to 2, 2 \to 1, 3 \to 3, 4 \to 4$ (4) $1 \to 2, 2 \to 1, 3 \to 4, 4 \to 3$ (5) $1 \to 3, 2 \to 4, 3 \to 1, 4 \to 2$ (6) $1 \to 3, 2 \to 4, 3 \to 2, 4 \to 1$ (7) $1 \to 4, 2 \to 3, 3 \to 1, 4 \to 2$ (8) $1 \to 4, 2 \to 3, 3 \to 2, 4 \to 1$

Constraints

For all test cases: $1 \le n \le 2 \cdot 10^3$, $0 \le m \le 10^3$, $1 \le k \le 10^{15}$; $1 \le u, v \le n$, $1 \le w \le m$; * It is guaranteed that the initially constructed $mn$ wormholes form a good construction plan.

Some test cases for this problem have large input sizes; we recommend using a fast I/O method.