很久以前，横滨的一条东西向道路旁坐落着许多 chayas（茶屋）。虽然茶屋的总数已知，但关于它们具体位置的信息却完全丢失了。

最近，人们发现了一份描述横滨旧时城镇景观的文档。该文档包含了一些关于茶屋位置顺序的记录。每条记录都提供了关于三座茶屋（记为 $a, b, c$）位置顺序的信息：

茶屋 $b$ 位于茶屋 $a$ 和 $c$ 之间。注意，$a$ 和 $b$ 之间，或者 $b$ 和 $c$ 之间可能还存在其他茶屋。此外，茶屋 $a$ 可能位于 $c$ 的东侧，也可能位于 $c$ 的西侧。

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

输入格式

输入包含单个测试用例，格式如下：

$n \ m$ $a_1 \ b_1 \ c_1$ $\vdots$ $a_m \ b_m \ c_m$

其中，$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)$。

输出格式

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

样例

样例输入 1

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

样例输出 1

4

说明 1

对于样例输入 1，有四种顺序 $(1, 5, 3, 2, 4), (4, 2, 3, 1, 5), (4, 2, 3, 5, 1)$ 和 $(5, 1, 3, 2, 4)$ 与记录相符。

样例输入 2

4 2
3 1 4
1 4 3

样例输出 2

0

说明 2

对于样例输入 2，不存在相符的顺序。