题目描述

Walk Alone 有一个包含 $n$ 个节点和 $m$ 条无向边的图。

他定义了一个函数：

$$f(u, v)=(\deg_u \oplus \deg_v) \times (\deg_u | \deg_v) \times (\deg_u \& \deg_v)$$

其中：

• $\deg_u$ 表示节点 $u$ 的度数（与该节点相连的边的数量）；
• $\oplus$ 表示按位异或，$|$ 表示按位或，$\&$ 表示按位与。

请你计算：

$$\left(\sum_{i=1}^n \sum_{j=i}^n f(i, j)\right) \bmod 998244353$$

输入格式

第一行输入两个整数 $n, m$（$1\le n\le 10^6,\ 0 \le m \le 10^6$），分别表示节点数量和边的数量。

接下来 $m$ 行，每行输入两个整数 $u, v$（$1 \le u, v \le n$），表示一条无向边 $(u, v)$。

注意：

1. 图中可能存在重边和自环；
2. 节点 $x$ 上的自环会为 $\deg_x$ 贡献 2。

输出格式

输出一个整数，表示答案对 $998244353$ 取模后的结果。

样例

输入 1

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

输出 1

30

限制

时间限制：1 秒 内存限制：1024KiB（每个测试用例）