#5473. 仙人掌

内存限制:512 MiB 时间限制:10 Sec

题目描述

有一个n个点,m个边的仙人掌。所谓仙人掌,就是任何一个点至多属于一个环。
每个边有1/2的概率被删掉。问期望剩下多少个边联通块。
所谓边联通块,就是问剩下的边,构成多少个联通块,单独一个点不算做联通块。
输出答案乘以2m之后mod1000000007的结果。

输入格式

第一行两个整数n,m。以下m行,每行两个整数x,y,表示树的一条边。
1≤n≤1000000。

输出格式

一行一个整数表示答案

样例

样例输入


			
3 2
1 2
2 3

样例输出


			
3

数据范围与提示