题目描述

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

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

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

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

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

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

由于答案很大，你只需要求出方案数除以 $998244353$ 的余数。

输入格式

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

接下来 $nm$ 行，每行三个正整数 $u,v,w$，表示一条编号为 $w$ 的，起点为 $u$ 号城市，终点为 $v$ 号城市的虫洞。

输出格式

输出一行整数，表示方案数除以 $998244353$ 的余数。

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

8

样例 1 解释

在该组样例中，已经建造的编号为 $1$ 的虫洞为 $1\to 2,2\to 1,3\to 4,4\to 3$。为了使 $8$ 条虫洞形成的建造方案是好的，新建造的编号为 $2$ 的虫洞可能有 $8$ 种情形：

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

样例 2

见选手目录下的 wormhole/wormhole2.in 和 wormhole/wormhole2.ans。

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

样例 3

见选手目录下的 wormhole/wormhole3.in 和 wormhole/wormhole3.ans。

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

样例 4

见选手目录下的 wormhole/wormhole4.in 和 wormhole/wormhole4.ans。

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

样例 5

见选手目录下的 wormhole/wormhole5.in 和 wormhole/wormhole5.ans。

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

样例 6

见选手目录下的 wormhole/wormhole6.in 和 wormhole/wormhole6.ans。

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

样例 7

见选手目录下的 wormhole/wormhole7.in 和 wormhole/wormhole7.ans。

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

样例 8

见选手目录下的 wormhole/wormhole8.in 和 wormhole/wormhole8.ans。

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

样例 9

见选手目录下的 wormhole/wormhole9.in 和 wormhole/wormhole9.ans。

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

样例 10

见选手目录下的 wormhole/wormhole10.in 和 wormhole/wormhole10.ans。

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

数据范围

对于所有测试点，

• $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$；
• 保证初始建造的 $mn$ 条虫洞构成一个号的建造方案。

测试点编号	$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$
$9\sim 10$		$\le 10$
$11\sim 14$			$\le 10^3$
$15\sim 16$		$=0$	$\le 10^{15}$
$17\sim 19$		$\le 10$
$20\sim 21$	$\le 2\cdot 10^3$	$\le 10^3$	$\le 10^2$
$22\sim 25$			$\le 10^{15}$

提示

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