Description

Walk Alone has a graph of $n$ nodes and $m$ bi-directional edges. He defines a function of $f(u, v)=(\deg_u \oplus \deg_v)(\deg_u | \deg_v)(\deg_u \& \deg_v)$, where ${\rm deg}_u$ denotes the number of edges that associated with node $u$, and $\oplus, |, \&$ denotes bitwise xor, bitwise or and bitwise and. He wants you to calculate $\left(\sum_{i=1}^n \sum_{j=i}^n f(i, j)\right) \bmod 998\ 244\ 353$.

Format

Input

The first line of the input contains two integers $n, m$ ($1\le n\le 10^6, 0 \le m \le 10^6$) denoting the number of nodes and edges.

Each of the following $m$ lines contains two integers $u, v$ ($1 \le u, v \le n$) representing a bi-directional edge $(u, v)$.

The graph might have duplicated edges and self-loops. Remind that a self-loop on node $x$ will contribute $2$ to $\deg_x$.

Output

Output a single integer denoting the answer.

Samples

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

30

Limitation

1s, 1024KiB for each test case.