Problem Description

Country E has $n$ cities, numbered from $1$ to $n$. To make travel between cities more convenient, the Ministry of Transportation of Country E wants to build some wormholes among the $n$ cities. Each wormhole is a directed passage from one city to another. The start and end of a passage are allowed to be the same city, and there may also be multiple wormholes connecting the same pair of cities.

To distinguish the construction time of wormholes, the ministry assigns each wormhole a positive integer label.

We call a wormhole construction plan good if it satisfies the following four conditions:

1. There exists a non-negative integer $d$ such that each city is the start of exactly $d$ wormholes and also the end of exactly $d$ wormholes.
2. For each city, among the labels of wormholes that start from it, $1$ to $d$ each appear exactly once.
3. For each city, among the labels of wormholes that end at it, $1$ to $d$ each appear exactly once.
4. Pick any city $u$ and positive integers $1\le j_1, j_2 \le d$. Starting from $u$, first go through a wormhole labeled $j_1$, then go through a wormhole labeled $j_2$, and arrive at city $v_1$. Starting from $u$, first go through a wormhole labeled $j_2$, then go through a wormhole labeled $j_1$, and arrive at city $v_2$. Then it must always hold that $v_1=v_2$.

In particular, the plan that builds no wormholes is also good.

Now, the builder has already built $mn$ wormholes and assigned them labels $1\sim m$, and the current construction plan is good. He wants to additionally build $kn$ wormholes and assign them labels $(m+1)\sim (m+k)$. He must ensure that all these $(m + k)n$ wormholes still form a good construction plan. He wants to know how many ways there are to build the new $kn$ wormholes such that the resulting plan of $(m + k)n$ wormholes is good.

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

Input Format

The first line contains four non-negative integers $c, n, m, k$, where $c$ denotes the test point ID. In the samples, $c$ means that the Constraints of that sample are the same as those of test point $c$.

In the next $nm$ lines, each line contains three positive integers $u, v, w$, representing a wormhole labeled $w$, with start city $u$ and end city $v$.

Output Format

Output one integer, the number of plans modulo $998244353$.

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

8

Hint

[Sample 1 Explanation]

In this sample, the already-built wormholes with label $1$ are $1\to 2,2\to 1,3\to 4,4\to 3$. To make the $8$ wormholes form a good construction plan, there are $8$ possible choices for the newly built wormholes with label $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$

[Sample 2]

See the attached wormhole2.in/ans.

This sample has $c = 2$, and it satisfies the constraints of test point 2.

[Sample 3]

See the attached wormhole3.in/ans.

This sample has $c = 5$, and it satisfies the constraints of test point 5.

[Sample 4]

See the attached wormhole4.in/ans.

This sample has $c = 7$, and it satisfies the constraints of test point 7.

[Sample 5]

See the attached wormhole5.in/ans.

This sample has $c = 9$, and it satisfies the constraints of test point 9.

[Sample 6]

See the attached wormhole6.in/ans.

This sample has $c = 11$, and it satisfies the constraints of test point 11.

[Sample 7]

See the attached wormhole7.in/ans.

This sample has $c = 15$, and it satisfies the constraints of test point 15.

[Sample 8]

See the attached wormhole8.in/ans.

This sample has $c = 17$, and it satisfies the constraints of test point 17.

[Sample 9]

See the attached wormhole9.in/ans.

This sample has $c = 20$, and it satisfies the constraints of test point 20.

[Sample 10]

See the attached wormhole10.in/ans.

This sample has $c = 22$, and it satisfies the constraints of test point 22.

[Subtasks]

For all test points,

• $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 built $mn$ wormholes form a good construction plan.

[Hint]

Some test points of this problem have large input sizes, so we recommend using a faster input method.

Translated by ChatGPT 5