시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB222100.000%

문제

Consider an undirected graph $G$ with $n$ vertices. A subset of its vertices is good if the total number of edges between them (edges such that both their ends are in this subset) is even. How many good sets are there? Since this number may be large, output it modulo prime number $998\,244\,353$.

입력

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

Each of the following $m$ lines contains two numbers $u$ and $v$ ($1 \le u, v \le n$): the vertices connected by an edge.

The graph is guaranteed to contain no loops or multiple edges.

출력

Output the number of good sets modulo $998\,244\,353$.

예제 입력 1

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

예제 출력 1

16

예제 입력 2

3 0

예제 출력 2

8

예제 입력 3

2 1
1 2

예제 출력 3

3

노트

In the second example, all sets are good. In the third example, the only non-good set is $\{1, 2\}$.