찻집

옛날 요코하마의 동서로 뻗은 도로 한쪽에 여러 채의 찻집(chaya)이 있었다. 찻집의 총 개수는 알려져 있지만, 각 찻집의 위치 정보는 완전히 유실되었다고 여겨졌다.

최근 요코하마의 옛 도시 풍경을 기록한 문서가 발견되었다. 이 문서에는 찻집의 위치 순서에 관한 기록이 여러 개 담겨 있다. 각 기록은 찻집 세 곳 $a$, $b$, $c$의 위치 순서에 대한 정보를 담고 있으며, 내용은 다음과 같다.

찻집 $b$는 찻집 $a$와 $c$ 사이에 있었다. $a$와 $b$ 사이, 또는 $b$와 $c$ 사이에 다른 찻집이 있었을 수 있다. 또한 찻집 $a$는 $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$번째 줄에는 1 이상 $n$ 이하의 서로 다른 정수 $a_i$, $b_i$, $c_i$가 주어진다. 이는 찻집 $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)$와 같지 않다. 즉, 같은 기록이 중복으로 주어지지 않는다.

기록과 모두 일치하는, 동쪽에서 서쪽 방향의 찻집 순서가 몇 가지인지 $998244353$으로 나눈 나머지를 한 줄에 출력한다. $998244353 = 2^{23} \times 7 \times 17 + 1$은 소수이다.

예제 입력 1에서는 $(1, 5, 3, 2, 4)$, $(4, 2, 3, 1, 5)$, $(4, 2, 3, 5, 1)$, $(5, 1, 3, 2, 4)$ 네 가지 순서가 기록과 일치한다.

예제 입력 2에서는 기록과 일치하는 순서가 없다.