# 有限跨度的管道

参考时间限制：1.5秒；内存限制：1024 MiB。实际时限取目标环境中最慢正式文件的标程中位耗时乘2，再按0.5秒向上取整。见[评测环境](../../../docs/评测环境与性能.md)。

## 背景故事

工程师在一排塔之间铺设管道。管道从高塔流向低塔，有些旧管道允许掉转方向。工程师希望知道，保留这些连接后，还能得到多少种布置。

(本故事由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$ .

![嵌套管道与不允许的交错端点](assets/example.svg)

## 输入格式

第一行三个整数 `n K M` .接下来 $M$ 行，每行三个整数 `u_i v_i e_i` .

## 输出格式

输出一个整数，表示方案数模 $998244353$ .


## 样例 1

### 输入

```text
13 9 2
2 3 1
5 7 0
```

### 输出

```text
2662
```

## 样例 2

### 输入

```text
6 5 2
1 6 0
2 3 1
```

### 输出

```text
6
```

## 样例 3

### 输入

```text
2 2 1
1 2 1
```

### 输出

```text
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%。[生成说明](tests/README.md)。