Keep It Cool

Time limit1sMemory limit512 MB

Summary

Count permutations of all pairs (a, b) with a < b that satisfy the betweenness rule for every triple and m given order constraints, modulo 998244353.

Level: Hard8 of 10
Topics: Dynamic programming, Bit manipulation
Solved: No attempts yet

Problem

Consider the set of all pairs $(a, b)$ where $a$ and $b$ satisfy $1 \leq a < b \leq n$ . A permutation of all these pairs is called balanced if, for any $a$ , $b$ , and $c$ with $1 \leq a < b < c \leq n$ , the pair $(a, c)$ lies between the pairs $(a, b)$ and $(b, c)$ in the permutation. That is, the three pairs appear either in the order $(a, b), (a, c), (b, c)$ , or in the order $(b, c), (a, c), (a, b)$ .

There are also $m$ additional restrictions. The $i$ -th restriction requires the pair $(a_i, b_i)$ to appear before the pair $(c_i, d_i)$ in the permutation. Count the balanced permutations that satisfy all $m$ restrictions.

Input

The first line contains two integers $n$ and $m$ ( $2 \le n \le 10$ , $0 \le m \le 10$ ). Each of the following $m$ lines contains four 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$ ). The pairs $(a_i, b_i)$ and $(c_i, d_i)$ are distinct.

Output

Print the number of balanced permutations where $(a_i, b_i)$ appears before $(c_i, d_i)$ for every $i$ , modulo the prime $998\,244\,353$ .

Hint

In the second sample, the valid permutations are $(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)$ and $(1,2), (1,3), (2,3), (1,4), (2,4), (3,4)$ .

Examples2

Example 1
Input
```
2 0
```
Expected output
```
1
```
Example 2
Input
```
4 3
1 2 2 3
1 2 3 4
2 3 3 4
```
Expected output
```
2
```