有限跨度的管道¶
参考时间限制：1.5秒；内存限制：1024 MiB。实际时限取目标环境中最慢正式文件的标程中位耗时乘2，再按0.5秒向上取整。见评测环境。
背景故事¶
工程师在一排塔之间铺设管道。管道从高塔流向低塔，有些旧管道允许掉转方向。工程师希望知道，保留这些连接后，还能得到多少种布置。
(本故事由GPT-6重写)
形式化问题描述¶
水平基线上有 \(n\) 个位置，编号 \(1,\ldots,n\) .每个位置可以不建塔，或建一座高度为 \(1,\ldots,K\) 中某个整数的竖直塔。每座塔的顶端必须恰好连接一根管道。
管道是两座不同位置的塔顶之间的直线段。两端高度必须不同，方向由高端指向低端。若端点位置为 \(u,v\) ，则 \(|u-v|\le K\) .管道之间不能相交或接触；管道除自己的两个端点外不能接触或穿过任何塔，但可以从塔顶上方严格越过。
已有 \(M\) 根管道，第 \(i\) 根记录为 \((u_i,v_i,e_i)\) .两个端点已经占用，必须保留它们的配对关系。当 \(e_i=1\) 时，方向固定为 \(u_i\to v_i\) ；当 \(e_i=0\) 时，可选两个方向之一。可以重新选择所有塔的高度，也可以在未占用位置增加新塔和新管道。
一个方案由所有管道的有序端点对集合确定。只改变塔高不产生新方案。求能用合法塔高实现的方案数量，模 \(998244353\) .
输入格式¶
第一行三个整数 n K M .接下来 \(M\) 行，每行三个整数 u_i v_i e_i .
输出格式¶
输出一个整数，表示方案数模 \(998244353\) .
样例 1¶
输入¶
13 9 2
2 3 1
5 7 0
输出¶
2662
样例 2¶
输入¶
6 5 2
1 6 0
2 3 1
输出¶
6
样例 3¶
输入¶
2 2 1
1 2 1
输出¶
1
数据范围与保证¶
\(2\le n\le10^6\) ，\(1\le K\le18\) ，\(1\le M\le\lfloor n/2\rfloor\) ，\(1\le u_i,v_i\le n\) ，\(u_i\ne v_i\) ，\(|u_i-v_i|\le K\) ，\(e_i\in\{0,1\}\) .
已有管道的所有端点互不相同，且存在合法塔高实现已有管道。因此合法输入实际上满足 \(K\ge2\) ：\(K=1\) 时无法放置任何高度不同的端点。
由 Codex（GPT-6）补齐并记录为重新设计：明确旧管道保留端点配对、所有高度均可重选、无塔位置可以空置，并补齐样例输出和接触规则。原有规模、模数和内存限制保留。
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |
共10个正式文件，每个10%。生成说明。