Description

从前，在横滨一条东西走向的道路一侧，有一系列 茶屋。尽管茶屋的总数是已知的，但它们位置的信息被认为已完全丢失。

最近，发现了一份描述横滨旧时街景的文献。这份文献包含了许多关于茶屋位置顺序的记录。每条记录都包含以下关于三个茶屋（设为 $a$、$b$ 和 $c$）位置顺序的信息：

茶屋 $b$ 位于茶屋 $a$ 和 $c$ 之间。注意，$a$ 和 $b$ 之间，或 $b$ 和 $c$ 之间可能还有其他茶屋。同时注意，茶屋 $a$ 可能位于 $c$ 的东边或西边。

我们想知道有多少种不同的茶屋沿道路排列的顺序与这份最近发现的文献中的所有记录一致。注意，由于记录可能存在错误，可能不存在与所有记录一致的顺序。

Input Format

输入由单个测试用例组成，格式如下。

$$\begin{aligned} &n\ m \\ &a_1\ b_1\ c_1 \\ &\vdots \\ &a_m\ b_m\ c_m \end{aligned}$$

这里，$n$ 表示茶屋的数量，$m$ 表示最近发现的文献中的记录数量。满足 $3 \le n \le 24$ 和 $1 \le m \le n \times (n - 1) \times (n - 2) / 2$。茶屋编号从 $1$ 到 $n$。

接下来的 $m$ 行，每行代表一条记录。第 $i$ 行包含三个互不相同的整数 $a_i$、$b_i$ 和 $c_i$，每个整数在 $1$ 到 $n$ 之间（含）。这表示茶屋 $b_i$ 位于茶屋 $a_i$ 和 $c_i$ 之间。没有两条记录具有相同的信息，即对于任意两个不同的整数 $i$ 和 $j$，三元组 $(a_i, b_i, c_i)$ 不等于 $(a_j, b_j, c_j)$ 或 $(c_j, b_j, a_j)$。

Output Format

在一行中输出与所有记录一致的茶屋从东到西的不同顺序的数量，结果对 $998\,244\,353$ 取模。注意 $998\,244\,353 = 2^{23} \times 7 \times 17 + 1$ 是一个质数。

5 4
1 2 4
2 3 5
3 2 4
1 3 2

4

4 2
3 1 4
1 4 3

0

Hint

翻译由 DeepSeek V3 完成