抽象代数

Problem Description

在 $U= \set{ 1, 2, \cdots, n }$ 上定义有结合律的二元运算 $\oplus$ 满足 $\forall a,b\in U, a\oplus b\in \{a,b\}$。 对于一个运算 $\oplus$，称数 $x$ 是交换子当且仅当 $\forall y\in U, x\oplus y=y\oplus x$。 已知 $m$ 个形如 $a\oplus b=c$ 的等式（$1\le a,b\le K\le 17$，$c\in \{a,b\}$），对于所有可能的 $\oplus$ 求 $2^{\text{交换子个数}}$ 和。

Input

首先输入三个自然数 $n,m,K$（$2\le n\le 10^5$，$0\le m \le K^2$，$1\le K\le 17$），分别表示元素个数、已知等式个数和已知等式的数字范围。 之后有 $m$ 行，每行有三个正整数 $a,b,c$（$1\le a,b\le K$，$c\in \{a,b\}$），表示一个等式 $a\oplus b=c$。

Output

输出一行一个自然数，表示答案除以 $998244353$ 的余数。

Sample Input

3 3 3
1 2 1
2 3 2
2 1 2

Sample Output

3

Hint

我们把已知信息列成一张表，未知部分用字母表示：

• $p=1,q=2$：符合题意，此时交换子有 $3$。
• $p=3,q=2$：$(3\oplus 1) \oplus 2 \ne 3 \oplus (1\oplus 2)$。
• $p=1,q=3$：$(3\oplus 2) \oplus 1 \ne 3 \oplus (2\oplus 1)$。
• $p=3,q=3$：符合题意，此时没有交换子。 因此你输出 $2^1+2^0=3$。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（9）