30932번 - Chayas 다국어

문제

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.

입력

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

$n$ $m$

$a_1$ $b_1$ $c_1$

$\vdots$

$a_m$ $b_m$ $c_m$

Here, $n$ represents the number of chayas and $m$ represents the number of records in the recently found document. 3ドル ≤ n ≤ 24$ and 1ドル ≤ m ≤ 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 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.

제한

힌트

For Sample Input 1, four orders, $(1, 5, 3, 2, 4),ドル $(4, 2, 3, 1, 5),ドル $(4, 2, 3, 5, 1),ドル and $(5, 1, 3, 2, 4),ドル are consistent with the records.

For Sample Input 2, there are no consistent orders.