代码:
#include<cstdio>
#include<vector>
#include<utility>
#include<algorithm>
#define int long long
int n,m,nn[500005],mm[500005],p[500005],d[500005],dp[500005][3],mod=1e9+7,base2[500005];
bool b[500005];
std::vector<std::vector<int> >v(500005),rv(500005);
std::vector<std::pair<int,int> >e;
int qu(int x){
if(x-p[x])p[x]=qu(p[x]);
return p[x];
}
void merge(int x,int y){
x=qu(x),y=qu(y);
if(x-y)p[x]=y,nn[y]+=nn[x];
}
void dfs(int now=1,int p=-1,int dd=0){
d[now]=dd;
b[now]=1;
for(int vv:v[now])if(vv-p){
if(b[vv])merge(now,vv),d[now]=std::min(d[now],d[vv]);
else{
dfs(vv,now,dd+1);
if(d[vv]<d[now])merge(now,vv),d[now]=std::min(d[now],d[vv]);
}
}
}
int mul(int a,int x){
if(!x)return 1;
int t=mul(a,x/2);
t=1ll*t*t%mod;
if(x%2)return 1ll*t*a%mod;
return t;
}
void dds(int now=1,int p=-1){
if(rv[now].size()==1&&now!=1){
dp[now][0]=base2[mm[now]];
dp[now][1]=base2[mm[now]+nn[now]]-dp[now][0];
dp[now][1]%=mod;
dp[now][1]+=mod;
dp[now][1]%=mod;
return;
}
dp[now][0]=base2[mm[now]];
dp[now][1]=base2[mm[now]];
for(int vv:rv[now])if(vv-p){
dds(vv,now);
dp[now][0]=(2ll*dp[vv][0]*dp[now][0])%mod;
dp[now][1]=(2ll*dp[vv][0]+dp[vv][1])*dp[now][1]%mod;
}
for(int vv:rv[now])if(vv-p){
dp[now][2]=(dp[now][2]+1ll*dp[now][0]*mul((2ll*dp[vv][0])%mod,mod-2)%mod*1ll*(dp[vv][1]+2ll*dp[vv][2])%mod)%mod;
//printf("%d:",1ll*dp[now][0]*mul((2ll*dp[vv][0])%mod,mod-2)%mod);
}
//printf("%d %d %d\n",dp[now][0],dp[now][1],dp[now][2]);
dp[now][1]=(((1ll*dp[now][1]*base2[nn[now]]-dp[now][0])%mod)+mod)%mod;
}
signed main(){
//printf("%d ",mul(2,10));
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++){//puts("*");
int u,v;
scanf("%lld%lld",&u,&v);
::v[v].push_back(u);
::v[u].push_back(v);
e.push_back(std::make_pair(u,v));
}
for(int i=1;i<=n;i++)p[i]=i,nn[i]=1;//puts("*");
dfs();
for(std::pair<int,int>zyh:e){
int x=zyh.first,y=zyh.second;
x=qu(x),y=qu(y);
if(x==y)mm[x]++;
else rv[x].push_back(y),rv[y].push_back(x);
}
base2[0]=1;
for(int i=1;i<=5e5;i++)base2[i]=(base2[i-1]<<1)%mod;
dds();
//for(int i=1;i<=n;i++)printf("%d %d %d\n",dp[i][0],dp[i][1],dp[i][2]);
printf("%d",(dp[1][1]+dp[1][2])%mod);
}