Description

jbgg 准备请 $n$ 个人吃饭(不包括他自己)，他们将会在一个可以坐 $n$ 个人的圆桌上吃饭，座位的编号从 $0$ 到 $n-1$ 按顺序围成一圈，对于坐在座位 $i$ 上的人，他可以吃到座位 $(i-1+n)\bmod n,i,(i+1)\bmod n$ 三个位置的菜，如果其中至少有一道菜是这个人喜欢的菜，那么他就会吃的很满意。

jbgg 选择的餐厅共有 $m$ 道菜，通过事先调查，jbgg 知道这 $n$ 个人每个人都有 $2$ 道喜欢吃的菜，为了让大家都吃的满意，他在每个人预定的座位前随机放了一道这个人喜欢吃的菜，同一种菜可以多次被放上餐桌。

粗心的 jbgg 虽然给所有人从 $0$ 到 $n-1$ 编了号，并打算让大家对号入座，但是通知时却忘了这回事，导致这些人最后都随机入座了。

jbgg 想知道最后吃的满意的人数的期望，以此来评估事情的严重性，聪明的你可以帮帮他吗?

请输出对 $998244353$ 取模后的答案。

Format

Input

第一行包含两个整数 $n,m\ (3\leqslant n,m \leqslant 5 \times 10^4)$,分别表示人数和菜的种类数。

接下来 $n$ 行，第 $i$ 行包含两个整数 $a_{i1},a_{i2}\ (1\leqslant a_{i1}< a_{i2} \leqslant m)$,表示原先编号为 $i-1$ 的人喜欢吃的两道菜。

Output

输出一个整数，表示期望。

有理数取模：如果答案是 $\frac{P}{Q}$ 的形式，若存在 $R$ 满足 $QR \equiv 1 \pmod {998244353}$，那么取模后的答案是 $PR \bmod 998244353$。

Samples

3 3
1 2
1 3
2 3

3

4 8
1 2
3 4
5 6
7 8

3

4 4
1 2
2 3
3 4
1 4

249561092

Notes

对于第一个样例，对每个人不管坐哪个位置都一定是满意的，因此期望为 $3$。

对于第二个样例，每个人都有 $\frac{3}{4}$ 的概率满足，因此期望为 $3$。

对于第三个样例，最后的期望为 $\frac{15}{4}$。

Limitation

3s, 256MB for each test case.