该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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程序设计竞赛现场赛