P11292 [MX-S6-T4] "KDOI-11" Colored Lights Party.

Original link: .

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

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.

Only one line: a non-negative integer, the sum of the beauty values over all $k^n$ configurations, modulo $998244353$.

**[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): | Index | Color of light $1$ | Color of light $2$ | Color of light $3$ | Beauty | |:--:|:--:|:--:|:--:|:--:| | $1$ | black | black | black | $4$ | | $2$ | black | black | white | $0$ | | $3$ | black | white | black | $1$ | | $4$ | black | white | white | $1$ | | $5$ | white | black | black | $1$ | | $6$ | white | black | white | $1$ | | $7$ | white | white | black | $0$ | | $8$ | white | white | white | $4$ | 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