题目背景

原题链接：https://oier.team/problems/96。

题目描述

小 K 家的房子还蛮大的，所以他举办了彩灯晚会。

彩灯晚会显然有彩灯。于是小 K 找来了 $n$ 盏彩灯。

小 K 不希望彩灯散在地上，于是他用 $m$ 条有向边连接了这些彩灯，使得他们连在一起。也就是说，在将有向边看成无向边的情况下，这些彩灯是连通的。保证该图为有向无环图。

小 K 的彩灯很厉害，每个都可以独立地发出 $k$ 种颜色中的任意一种。小 K 作为世界顶尖 Light Glowing Master（简称 LGM），决定将所有方案（共 $k^n$ 种）都尝试一下。

小 K 不喜欢很多的颜色，于是他给定了一个正整数 $l$，并定义一个方案的美丽度为每种颜色长度为 $l$ 的链数量的平方之和。形式化地讲，设第 $i$ 种颜色的长度为 $l$ 的链的数量为 $cnt_i$，则一个方案的美丽度为 $\sum_{i=1}^kcnt_i^2$。

现在小 K 想知道所有 $k^n$ 种方案的美丽度之和，对 $998244353$ 取模。

两种方案是不同的当且仅当存在某个彩灯在两种方案中发出不同的颜色。

一条长度为 $l$ 的链是一个 $2l-1$ 元组 $(v_1,e_1,v_2,e_2,\dots,e_{l-1},v_l)$，使得对于任意 $1\leq i<l$，第 $e_i$ 条有向边是由 $v_i$ 连向 $v_{i+1}$ 的。两条长度为 $l$ 的链 $(v_1,e_1,v_2,e_2,\dots,e_{l-1},v_l)$ 和 $(v'_1,e'_1,v'_2,e'_2,\dots,e'_{l-1},v'_l)$ 不同当且仅当存在 $1\leq i<l$ 满足 $e_i\neq e'_i$ 或存在 $1\leq i\leq l$ 满足 $v_i\neq v'_i$。

一种颜色 $x$ 的长度为 $l$ 的链是一条长度为 $l$ 的链 $(v_1,e_1,v_2,e_2,\dots,e_{l-1},v_l)$ 使得对于任意 $1\leq i\leq l$，$v_i$ 编号的彩灯发出颜色为 $x$。

输入格式

第一行，五个非负整数 $id,n,k,l,M$，其中 $id$ 表示测试点编号（所有样例满足 $id=0$），$n$ 表示彩灯数量，$k$ 表示颜色数量，$l$ 表示链的长度，$M$ 的意义如后文所示。

接下来 $M$ 行，第 $i$ 行三个正整数 $u_i,v_i,c_i$，表示有 $c_i$ 条 $u_i\to v_i$ 的有向边。也就是说，第 $\bigl(\sum_{j=1}^{i-1}c_j\bigr)+1$ 至第 $\bigl(\sum_{j=1}^ic_j\bigr)$ 条有向边由 $u_i$ 连向 $v_i$。

题面中 $m$ 满足 $m=\sum_{i=1}^Mc_i$。保证：$(u,v)$ 互不相同，给定图为有向无环图，在将有向边看成无向边的情况下，彩灯是连通的。

输出格式

仅一行，一个非负整数，表示所有 $k^n$ 种方案的美丽度之和，对 $998244353$ 取模。

0 3 2 2 2
1 3 1
3 2 1

12

0 5 4 3 7
1 4 4
1 5 2
4 3 1
5 3 2
3 2 3
4 5 1
5 2 2

16096

提示

【样例解释 #1】

共有 $2^3=8$ 种不同的彩灯显示颜色的方案，如下表所示（不妨假设颜色为黑和白）：

编号	$1$ 号彩灯颜色	$2$ 号彩灯颜色	$3$ 号彩灯颜色	美丽度
$1$	黑	黑	黑	$4$
$2$			白	$0$
$3$		白	黑	$1$
$4$			白
$5$	白	黑	黑
$6$			白
$7$		白	黑	$0$
$8$			白	$4$

美丽度之和为 $4+0+1+1+1+1+0+4=12$。

【样例 #3】

见附件中的 party/party3.in 与 party/party3.ans。

该组样例满足测试点 $1$ 的约束条件。

【样例 #4】

见附件中的 party/party4.in 与 party/party4.ans。

该组样例满足测试点 $2\sim3$ 的约束条件。

【样例 #5】

见附件中的 party/party5.in 与 party/party5.ans。

该组样例满足测试点 $4\sim5$ 的约束条件。

【样例 #6】

见附件中的 party/party6.in 与 party/party6.ans。

该组样例满足测试点 $6\sim9$ 的约束条件。

【样例 #7】

见附件中的 party/party7.in 与 party/party7.ans。

该组样例满足测试点 $10\sim12$ 的约束条件。

【样例 #8】

见附件中的 party/party8.in 与 party/party8.ans。

该组样例满足测试点 $13\sim15$ 的约束条件。

【样例 #9】

见附件中的 party/party9.in 与 party/party9.ans。

该组样例满足测试点 $20\sim21$ 的约束条件。

【数据范围】

记 $P=998244353$，对于所有测试数据，保证：$1\leq n\leq300$，$1\leq M\leq\frac{n(n-1)}{2}$，$1\leq k<P$，$1\leq l\leq 20$，$1\leq c_i<P$，$(u_i,v_i)$ 互不相同，给定图为有向无环图，在将有向边看成无向边的情况下，彩灯是连通的。

测试点编号	$n\leq$	$k\leq$	$l\leq$	特殊性质
$1$	$6$			$m\leq10$，$c_i=1$
$2\sim3$	$300$	$P-1$	$1$	无
$4\sim5$			$2$
$6\sim9$			$3$
$10\sim12$			$20$	$M=n-1$ 且有且仅有一个点入度为 $0$
$13\sim15$	$30$		$10$	无
$16$	$150$		$7$
$17$			$10$
$18\sim19$			$13$
$20\sim21$	$300$		$9$
$22$			$13$
$23$			$16$
$24\sim25$			$20$