20599번 - Keep It Cool 다국어

문제

Consider the set of all pairs $(a, b)$ with $a$ and $b$ satisfying the constraint 1ドル \leq a < b \leq n$. A permutations of all these pairs is called balanced if and only if, for any $a,ドル $b$ and $c$ satisfying 1ドル \leq a < b < c \leq n,ドル the pair $(a, c)$ is between the pairs $(a, b)$ and $(b, c)$ in the permutation. That is, those three pairs appear in the permutation either in the order $(a, b), (a, c), (b, c),ドル or in the order $(b, c), (a, c), (a, b)$.

Moreover, there are $m$ additional restrictions on the permutation, $i$-th of them states that the pair $(a_i, b_i)$ should appear before the pair $(c_i, d_i)$ in the permutation. Compute the number of balanced permutations that satisfy these $m$ restrictions.

입력

In the first line of the input, there are space-separated integers $n$ and $m$ (2ドル \le n \le 10$; 0ドル \le m \le 10$). The $i$-th of the following $m$ lines contains space-separated integers $a_i,ドル $b_i,ドル $c_i,ドル and $d_i$ (1ドル \le a_i < b_i \le n$; 1ドル \le c_i < d_i \le n$; pairs $(a_i, b_i)$ and $(c_i, d_i)$ are different).

출력

Print the number of balanced permutations where $(a_i, b_i)$ appears before $(c_i, d_i)$ for every $i$. As this number can be very large, print it modulo prime number 998ドル,244円,353円$.

제한

힌트

In the second sample, the permutations are: $(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)$; $(1,2), (1,3), (2,3), (1,4), (2,4), (3,4)$.