Problem Description

A permutation of length $n$ is defined as a sequence $p_1, p_2, \dots, p_n$ where each integer in the range $[1, n]$ appears exactly once. An inversion pair in a permutation is defined as a pair of integers $(i, j)$ where $i, j \in [1, n]$ and $i < j$ with $p_i > p_j$.

An inversion graph is defined as a graph with $n$ vertices, where there is an edge between vertices $i$ and $j$ if and only if $(i, j)$ is an inversion pair.

A independent set in a graph is defined as a set of vertices where no two vertices in the set are connected by an edge. A dominating set in a graph is defined as a set of vertices where every vertex not in the set is connected to at least one vertex in the set. An independent dominating set is defined as a set of vertices that is both an independent set and a dominating set.

Given the inversion graph of a permutation of length $n$, calculate the number of independent dominating sets in this graph.

The answer is guaranteed to be no more than $10^{18}$.

Input Format

The first line contains two integers $n$ and $m$ $(1 \leq n \leq 100, 0 \leq m \leq \frac{n \times (n-1)}{2})$, representing the number of vertices and edges in the graph, respectively.

The next $m$ lines each contain two integers $u_i$ and $v_i$ $(1 \leq u_i, v_i \leq n)$, indicating that there is an edge between vertex $u_i$ and vertex $v_i$.

The input guarantees that the graph corresponds to a permutation.

Output Format

Output the number of independent dominating sets in the graph.

The answer is guaranteed to be no more than $10^{18}$.

Sample Input and Output

Sample Input #1

4 2
2 3
2 4

Sample Output #1

2

Sample Input #2

5 7
2 5
1 5
3 5
2 3
4 1
4 3
4 2

Sample Output #2

3

Sample Input #3

7 7
5 6
2 3
6 7
2 7
3 1
7 5
7 4

Sample Output #3

6

Sample Input #4

5 6
1 3
4 5
1 4
2 3
1 2
1 5

Sample Output #4

5

Notes

In the first sample, the graph corresponds to the permutation $[1, 4, 2, 3]$, and the independent dominating sets are $(1, 3, 4)$ and $(1, 2)$.

In the second sample, the graph corresponds to the permutation $[3, 5, 4, 1, 2]$, and the independent dominating sets are $(1, 2)$, $(1, 3)$, and $(4, 5)$.

In the third sample, the graph corresponds to the permutation $[2, 4, 1, 5, 7, 6, 3]$.

In the fourth sample, the graph corresponds to the permutation $[5, 2, 1, 4, 3]$.

见题面 Input 部分

见题面 Output 部分