Background

Original link: https://oier.team/problems/S6D.

Problem Description

Little K’s house is quite large, so he is holding a colored lights party.

A colored lights party obviously needs colored lights. So Little K found $n$ colored lights.

Little K does not want the lights scattered on the ground, so he connected these lights with $m$ directed edges so that they are connected together. That is, if we treat the directed edges as undirected edges, then these lights form a connected graph. It is guaranteed that this graph is a directed acyclic graph (DAG).

Little K’s lights are very powerful: each one can independently emit any one of $k$ colors. As a world-class Light Glowing Master (LGM for short), Little K decided to try all configurations (there are $k^n$ in total).

Little K does not like having too many colors, so he is given a positive integer $l$, and defines the beauty of a configuration as the sum of squares of the number of length-$l$ chains of each color. Formally, let the number of length-$l$ chains of the $i$-th color be $cnt_i$, then the beauty of a configuration is $\sum_{i=1}^kcnt_i^2$.

Now Little K wants to know, over all $k^n$ configurations, the sum of their beauty values, modulo $998244353$.

Two configurations are different if and only if there exists some light that emits different colors in the two configurations.

A length-$l$ chain is a $(2l-1)$-tuple $(v_1,e_1,v_2,e_2,\dots,e_{l-1},v_l)$ such that for any $1\leq i<l$, the $e_i$-th directed edge goes from $v_i$ to $v_{i+1}$. Two length-$l$ chains $(v_1,e_1,v_2,e_2,\dots,e_{l-1},v_l)$ and $(v'_1,e'_1,v'_2,e'_2,\dots,e'_{l-1},v'_l)$ are different if and only if there exists some $1\leq i<l$ with $e_i\neq e'_i$, or there exists some $1\leq i\leq l$ with $v_i\neq v'_i$.

A length-$l$ chain of color $x$ is a length-$l$ chain $(v_1,e_1,v_2,e_2,\dots,e_{l-1},v_l)$ such that for every $1\leq i\leq l$, the light with index $v_i$ emits color $x$.

Input Format

The first line contains five non-negative integers $id,n,k,l,M$, where $id$ is the test point index (all samples satisfy $id=0$), $n$ is the number of lights, $k$ is the number of colors, $l$ is the chain length, and the meaning of $M$ is described below.

The next $M$ lines: the $i$-th line contains three positive integers $u_i,v_i,c_i$, meaning there are $c_i$ directed edges $u_i\to v_i$. That is, the $\bigl(\sum_{j=1}^{i-1}c_j\bigr)+1$-th through the $\bigl(\sum_{j=1}^ic_j\bigr)$-th directed edges go from $u_i$ to $v_i$.

In the statement, $m$ satisfies $m=\sum_{i=1}^Mc_i$. It is guaranteed that: all pairs $(u,v)$ are distinct, the given graph is a DAG, and if directed edges are treated as undirected, the lights form a connected graph.

Output Format

Only one line: a non-negative integer, the sum of the beauty values over all $k^n$ configurations, modulo $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

Hint

[Sample Explanation #1]

There are $2^3=8$ different configurations of light colors, shown in the table below (assume the colors are black and white):

The sum of beauty values is $4+0+1+1+1+1+0+4=12$.

[Sample #3]

See party/party3.in and party/party3.ans in the attachment.

This sample satisfies the constraints of test point $1$.

[Sample #4]

See party/party4.in and party/party4.ans in the attachment.

This sample satisfies the constraints of test points $2\sim3$.

[Sample #5]

See party/party5.in and party/party5.ans in the attachment.

This sample satisfies the constraints of test points $4\sim5$.

[Sample #6]

See party/party6.in and party/party6.ans in the attachment.

This sample satisfies the constraints of test points $6\sim9$.

[Sample #7]

See party/party7.in and party/party7.ans in the attachment.

This sample satisfies the constraints of test points $10\sim12$.

[Sample #8]

See party/party8.in and party/party8.ans in the attachment.

This sample satisfies the constraints of test points $13\sim15$.

[Sample #9]

See party/party9.in and party/party9.ans in the attachment.

This sample satisfies the constraints of test points $20\sim21$.

[Constraints]

Let $P=998244353$. For all testdata, it is guaranteed that: $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$, all pairs $(u_i,v_i)$ are distinct, the given graph is a DAG, and if directed edges are treated as undirected, the lights form a connected graph.

Translated by ChatGPT 5