Once upon a time, there was a "toxic" person.

This person recently discovered the secret to mass-producing "toxic" problems. Consider the following type of data structure problem: given an array, support several strange modification operations (such as adding $c$ to all numbers in a range, or taking the square root of all numbers in a range), and support queries for the sum of a range. The person considered $n$ such modification operations and numbered them $1 \sim n$. When they want to create a data structure problem, they select a subset of these operations to form a problem.

Of course, such problems might be unsolvable. Through exquisite mathematical reasoning, the person revealed the relationships between these modification operations: there are $m$ pairs of "mutually exclusive" modification operations, where the $i$-th pair consists of the $u_i$-th operation and the $v_i$-th operation. If a problem contains both $u_i$ and $v_i$, the problem becomes unsolvable. On the other hand, if a problem does not contain any "mutually exclusive" operations, the problem is solvable. Furthermore, the person discovered a rule: $m - n$ is a very small number (see the "Constraints" section for details), and any two modification operations are connected. Two modification operations $a, b$ are connected if and only if there exist operations $t_0, t_1, \dots, t_l$ such that $t_0 = a$, $t_l = b$, and for any $1 \le i \le l$, $t_{i-1}$ and $t_i$ are a "mutually exclusive" pair.

A pair of "mutually exclusive" modification operations is called an exclusive pair. Now, given the values of $n$ and $m$ exclusive pairs, the person wants to know how many different solvable data structure problems they can create. Two data structure problems are different if and only if there is an operation that appears in one problem but not in the other.

Input

The first line contains two positive integers $n, m$.

The next $m$ lines each contain two positive integers $u, v$, representing a pair of "mutually exclusive" modification operations.

Output

Output a single integer representing the number of different solvable data structure problems that can be created. Since this number may be very large, output the value modulo $998244353$.

Examples

Input 1

3 2
1 2
2 3

Output 1

5

Note 1

The solvable data structure problems are: the empty set, $\{1\}$, $\{2\}$, $\{3\}$, $\{1, 3\}$. Note: the empty set is a valid data structure problem.

Input 2

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

Output 2

16

Input 3

12 18
12 6
3 11
8 6
2 9
10 4
1 8
6 2
11 5
10 6
12 2
9 3
7 6
2 7
3 2
7 3
5 6
2 11
12 1

Output 3

248

Constraints

For all data, $n \le 10^5$, $n - 1 \le m \le n + 10$.