You are given an undirected graph with $n$ vertices and $m$ edges. You want to choose a non-empty subset of vertices such that the subgraph induced by this subset (containing only the chosen vertices and the edges whose both endpoints are in the subset) is connected. You want to know how many such subsets exist.

Since the problem setter is not malicious, the answer is not taken modulo $998244353$, but rather modulo $2$.

Input

The first line contains two positive integers $n$ and $m$, representing the number of vertices and edges in the graph.

The next $m$ lines each contain two positive integers $a_i, b_i$, representing an edge.

Output

Output a single integer representing the answer.

Examples

Input 1

3 2
1 2
2 3

Output 1

0

Note

The answer before taking the modulo is $6$. The chosen subsets are $\{1\}, \{2\}, \{3\}, \{1,2\}, \{2,3\}, \{1,2,3\}$.

Subtasks

Subtask 1 (30%): $1 \le n \le 18$;

Subtask 2 (30%): $1 \le |a_i - b_i| \le 7$;

Subtask 3 (40%): No special restrictions.

For 100% of the data, $1 \le n \le 50$, $0 \le m \le \frac{n(n-1)}{2}$, $1 \le |a_i - b_i| \le 12$.