在 $U= \{ 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{交换子个数}}$ 和。
首先输入三个自然数 $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$。
输出一行一个自然数，表示答案除以 $998244353$ 的余数。
我们把已知信息列成一张表，未知部分用字母表示：
| $a$ \ $a\oplus b$ \ $b$ | $1$ | $2$ | $3$ |
|---|---|---|---|
| $1$ | $\boxed{1}$ | $1$ | $\color{green}{1}$ |
| $2$ | $2$ | $\boxed{2}$ | $2$ |
| $3$ | $p$ | $q$ | $\boxed{3}$ |
其中，方框内数字由“$a\oplus b\in \{a,b\} $”可以自动得到；黑色数字是输入的条件。
现在还有两个空 $p,q$ 没填，对两个空进行枚举：
因此你输出 $2^1+2^0=3$。