Background

某一天，坤坤与他的哥哥互动。
坤坤：“出一道我不会的图论题！”。
哥哥：“你吼那么大声干什么嘛！来，知道线图吗，一个无向图$G$的线图记作$L(G)$。$L(G)$的每个点唯一对应$G$中的一条边，$L(G)$中两个点之间有边当且仅当这两个点对应的边在$G$中有公共点。”
坤坤：“你到底在说什么？”
哥哥：“看看图，图中形象地给出了如何求一个图的线图。”

Description

上文中哥哥讲到的线图操作也可以多次复合，比如求$L(L(L(G)))$。
哥哥觉得这个东西够抽象了，于是哥哥给弟弟的题目就是，给出$G$，求$L(L(L(G)))$的点数。

Format

Input

每个测试点仅包含一组输入数据。
第一行一个整数$n,m(n<=1000000,m<=2000000)$，表示$G$的点数和边数。
接下来$m$行，每行三个用空格隔开的整数$u,v(1<=u,v<=n)$，表示$G$中一条无向边连接$(u,v)$。
保证$G$无重边或自环。

Output

输出仅一行一个整数，为答案除以$63246324$所得余数。

Sample 1

Input

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

Output

19

Limitation

1s, 1GB for each test case.

Source

2019网宿杯XMU程序设计竞赛现场赛