Description

Once upon a time, there were a number of chayas (teahouses) along one side of an east-west road in Yokohama. Although the total number of chayas is known, the information about their locations was considered to be lost totally.

Recently, a document describing the old townscapes of Yokohama has been found. The document contains a number of records on the order of the locations of chayas. Each record has information below on the order of the locations of three chayas, say $a$, $b$, and $c$.

Chaya $b$ was located between chayas $a$ and $c$. Note that there may have been other chayas between $a$ and $b$, or between $b$ and $c$. Also, note that chaya $a$ may have been located east of $c$ or west of $c$.

We want to know how many different orders of chayas along the road are consistent with all of these records in the recently found document. Note that, as the records may have some errors, there might exist no orders consistent with the records.

Input Format

The input consists of a single test case given in the following format.

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

Here, $n$ represents the number of chayas and $m$ represents the number of records in the recently found document. $3 \le n \le 24$ and $1 \le m \le n \times (n - 1) \times (n - 2) / 2$ hold. The chayas are numbered from 1 to $n$.

Each of the following $m$ lines represents a record. The $i$-th of them contains three distinct integers $a_i$, $b_i$, and $c_i$, each between 1 and $n$, inclusive. This says that chaya $b_i$ was located between chayas $a_i$ and $c_i$. No two records have the same information, that is, for any two different integers $i$ and $j$, the triple $(a_i, b_i, c_i)$ is not equal to $(a_j, b_j, c_j)$ nor $(c_j, b_j, a_j)$.

Output Format

Output the number of different orders of the chayas, from east to west, consistent with all of the records modulo $998\,244\,353$ in a line. Note that $998\,244\,353 = 2^{23} \times 7 \times 17 + 1$ is a prime number.

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

4

4 2
3 1 4
1 4 3

0