H. Binary Craziness
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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$$$.

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.

Examples
Input
6 6
1 3
2 3
1 4
2 5
3 6
4 6
Output
30
Input
6 4
1 2
3 5
2 4
3 6
Output
0