#SXLK2024C. 虫洞

虫洞

题目描述

E 国有 nn 个城市,编号为 11nn。为了让城市之间的来往更加便利,E 国的交通部想在 nn 个城市间建造一些虫洞。每条虫洞是一条单向的从某个城市到另一个城市的通道。允许通道的起点和终点是同一个城市,也允许两个城市之间有多个虫洞连接。

为了区分虫洞的建造时间,交通部给每一条虫洞一个正整数的编号。

我们称一种虫洞的建造方案是好的,若它满足如下四个条件:

  1. 存在一个非负整数 dd 使得每个城市恰好是 dd 条虫洞的起点,也恰好是 dd 条虫洞的终点。
  2. 对于每个城市而言,在以它为起点的虫洞的编号中,11dd 恰好各出现一次。
  3. 对于每个城市而言,在以它为终点的虫洞的编号中,11dd 恰好各出现一次。
  4. 任意选取一个城市 uu 和正整数 1j1,j2d1\le j_1, j_2 \le d。设从 uu 出发,先经过一次编号为 j1j_1 的虫洞,再经过一次编号为 j2j_2 的虫洞,到达城市 v1v_1。设从 uu 出发,先经过一次编号为 j2j_2 的虫洞,再经过一次编号为 j1j_1 的虫洞,到达城市 v2v_2。则条件 v1=v2v_1=v_2 必定满足。

特别地,不建造任何虫洞的方案也是好的。

现在,建造师已建造了 mnmn 条虫洞,且给了它们 1m1\sim m 的编号,此时这样的建造方案是好的。他想要新建造 knkn 条虫洞,并给它们 (m+1)(m+k)(m+1)\sim (m+k) 的编号。他必须保证这 (m+k)n(m + k)n 条虫洞形成的建造方案仍然是好的。他想知道有多少种新建造 knkn 条虫洞的方法,使得这 (m+k)n(m + k)n 条虫洞形成的建造方案是好的。

由于答案很大,你只需要求出方案数除以 998244353998244353 的余数。

输入格式

输入的第一行四个非负整数 c,n,m,kc, n, m, k,其中 cc 表示测试点编号。样例中的 cc 表示该样例的数据范围与第 cc 个测试点的数据范围相同。

接下来 nmnm 行,每行三个正整数 u,v,wu,v,w,表示一条编号为 ww 的,起点为 uu 号城市,终点为 vv 号城市的虫洞。

输出格式

输出一行整数,表示方案数除以 998244353998244353 的余数。

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

【样例 1 解释】

在该组样例中,已经建造的编号为 11 的虫洞为 12,21,34,431\to 2,2\to 1,3\to 4,4\to 3。为了使 88 条虫洞形成的建造方案是好的,新建造的编号为 22 的虫洞可能有 88 种情形:

  1. 11,22,33,441\to 1, 2\to 2, 3\to 3, 4\to 4
  2. 11,22,34,431\to 1, 2\to 2, 3\to 4, 4\to 3
  3. 12,21,33,441\to 2, 2\to 1, 3\to 3, 4\to 4
  4. 12,21,34,431\to 2, 2\to 1, 3\to 4, 4\to 3
  5. 13,24,31,421\to 3, 2\to 4, 3\to 1, 4\to 2
  6. 13,24,32,411\to 3, 2\to 4, 3\to 2, 4\to 1
  7. 14,23,31,421\to 4, 2\to 3, 3\to 1, 4\to 2
  8. 14,23,32,411\to 4, 2\to 3, 3\to 2, 4\to 1

【样例 2】

见附件中的 wormhole2.in/ans

该样例的 c=2c = 2,它满足第 2 个测试点的限制条件。

【样例 3】

见附件中的 wormhole3.in/ans

该样例的 c=5c = 5,它满足第 5 个测试点的限制条件。

【样例 4】

见附件中的 wormhole4.in/ans

该样例的 c=7c = 7,它满足第 7 个测试点的限制条件。

【样例 5】

见附件中的 wormhole5.in/ans

该样例的 c=9c = 9,它满足第 9 个测试点的限制条件。

【样例 6】

见附件中的 wormhole6.in/ans

该样例的 c=11c = 11,它满足第 11 个测试点的限制条件。

【样例 7】

见附件中的 wormhole7.in/ans

该样例的 c=15c = 15,它满足第 15 个测试点的限制条件。

【样例 8】

见附件中的 wormhole8.in/ans

该样例的 c=17c = 17,它满足第 17 个测试点的限制条件。

【样例 9】

见附件中的 wormhole9.in/ans

该样例的 c=20c = 20,它满足第 20 个测试点的限制条件。

【样例 10】

见附件中的 wormhole10.in/ans

该样例的 c=22c = 22,它满足第 22 个测试点的限制条件。

【子任务】

对于所有测试点,

  • 1n21031\le n \le 2\cdot 10^30m1030 \le m \le 10^31k10151 \le k \le 10^{15}
  • 1u,vn1 \le u,v \le n1wm1 \le w \le m
  • 保证初始建造的 mnmn 条虫洞构成一个号的建造方案。
测试点编号 nn mm kk
141\sim 4 5\le 5 3\le 3 3 \le 3
565\sim 6 2103\le 2\cdot 10^3 =0=0 =1=1
787\sim 8 102\le 10^2 =1 =1
9109\sim 10 10\le 10
111411\sim 14 103\le 10^3
151615\sim 16 =0=0 1015\le 10^{15}
171917\sim 19 10\le 10
202120\sim 21 2103\le 2\cdot 10^3 103\le 10^3 102\le 10^2
222522\sim 25 1015\le 10^{15}

【提示】

本题部分测试点输入规模较大,我们推荐你使用较为快速的读入方式。