题目描述

某星球国家共有 $n$ 个城市，编号 $1$ 至 $n$ ，第 $i$ 个城市有 $i$ 个市民。一开始所有城市之间都不连通。

现在进行 $y$ 年道路建设期，编号 $1$ 至 $Y$ ，在第 $i$ 年的 $6$ 月份，会建好一条道路，链接城市 $A_i$ 和 $B_i$ ，同年 $12$ 月份，国家的每个市民都会向全国的其他每一个市民寄一张贺卡，如果道路能送达（即有路径到达），那么贺卡就会被寄出，否则贺卡会被邮局销毁。问题是：$Y$ 年建设期总共有多少贺卡会被寄出？答案模 $1000000007$ 。

输入格式

第 $1$ 行，两个整数，$n$，$y$ ($1 \le n,y \le 10^5$ )

从第 $2$ 到第 $y+1$ 行，有 两个整数 $u$, $v$，第 $i+1$ 行表示第 $i$ 年 $6$ 月份，城市 $u$ 和 $v$ 之间会建好一条道路。注意，有可能两个城市之间不止一条道路。

输出格式

一个整数。

样例

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

678