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)$.