P10219 [Joint Provincial NOI Qualifier 2024] Wormhole

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$.

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 one integer, the number of plans modulo $998244353$.

**[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. | Test point ID | $n$ | $m$ | $k$ | | :--: | :--: | :--: | :--: | | $1\sim 4$ | $\le 5$ | $\le 3$ |$ \le 3$ | | $5\sim 6$ | $\le 2\cdot 10^3$| $=0$ | $=1$| | $7\sim 8$ | $\le 10^2$ | $=1$| $=1$ | | $9\sim 10$ | $\le 10^2$ | $\le 10$ | $=1$| | $11\sim 14$ | $\le 10^2$ | $\le 10$ | $\le 10^3$| | $15\sim 16$ | $\le 10^2$ | $=0$ | $\le 10^{15}$ | | $17\sim 19$ | $\le 10^2$ | $\le 10$ | $\le 10^{15}$ | | $20\sim 21$ | $\le 2\cdot 10^3$ | $\le 10^3$ | $\le 10^2$ | | $22\sim 25$ | $\le 2\cdot 10^3$ | $\le 10^3$ | $\le 10^{15}$ | **[Hint]** Some test points of this problem have large input sizes, so we recommend using a faster input method. Translated by ChatGPT 5