#include<bits/stdc++.h> #define ppc __builtin_popcount using namespace std; const int N=105,mod=1e9+7,iv2=(mod+1)/2,MS=4.3e6; int n,m; int x[N],y[N],p2[N],ivp2[N],c[N],rk[N];bool vis[N]; int c1[MS],c2[MS],S1[MS],S2[MS]; int main(){ //freopen("silksong.in","r",stdin); //freopen("silksong.out","w",stdout); cin>>n>>m; for(int i=1;i<=m;i++){ cin>>x[i]>>y[i]; }p2[0]=1; for(int i=1;i<=m;i++) p2[i]=2ll*p2[i-1]%mod; ivp2[0]=1; for(int i=1;i<=m;i++) ivp2[i]=1ll*ivp2[i-1]*iv2%mod; if(n<=22){ int U=(1<<n)-1; int ans=0; for(int i=0;i<=U;i++){ int cnt=m; for(int j=1;j<=m;j++){ bool ok=0; if((i>>(x[j]-1))&1) ok=1; if((i>>(y[j]-1))&1) ok=1; cnt-=ok; } if(ppc(i)&1) ans=(ans+mod-p2[cnt])%mod; else ans=(ans+p2[cnt])%mod; }cout<<ans<<endl; }else{ int n1=21,n2=n-n1; for(int i=1;i<=n;i++) c[i]=(i>n1); mt19937_64 rng(21119002); int T=0,ans=0; while(T<=300000){ shuffle(c+1,c+n+1,rng); //for(int i=1;i<=n;i++) cout<<c[i]<<' ';cout<<endl; int cnt=0; for(int i=1;i<=m;i++){ if(c[x[i]]!=c[y[i]]) cnt++; } if(cnt<=22) break;T++; } //cout<<T<<endl; vector<int> id1,id2,ide; for(int i=1;i<=n;i++){ if(c[i]) id2.push_back(i); else id1.push_back(i); } for(int i=0;i<n1;i++) rk[id1[i]]=i; for(int i=0;i<n2;i++) rk[id2[i]]=i; int U1=(1<<n1)-1,U2=(1<<n2)-1; for(int i=0;i<=U1;i++){ int cnt=0; for(int j=0;j<n1;j++) if((i>>j)&1) vis[id1[j]]=1; for(int j=1;j<=m;j++){ if(vis[x[j]]||vis[y[j]]) cnt++; } for(int j=0;j<n1;j++) if((i>>j)&1) vis[id1[j]]=0; c1[i]=ivp2[cnt];if(ppc(i)&1) c1[i]=(mod-c1[i])%mod; } for(int i=0;i<=U2;i++){ int cnt=0; for(int j=0;j<n2;j++) if((i>>j)&1) vis[id2[j]]=1; for(int j=1;j<=m;j++){ if(vis[x[j]]||vis[y[j]]) cnt++; } for(int j=0;j<n2;j++) if((i>>j)&1) vis[id2[j]]=0; c2[i]=ivp2[cnt];if(ppc(i)&1) c2[i]=(mod-c2[i])%mod; } for(int i=0;i<n1;i++){ for(int j=0;j<U1;j++){ if((j>>i)&1) continue; c1[j]=(c1[j]+c1[j+(1<<i)])%mod; } } for(int i=0;i<n2;i++){ for(int j=0;j<U2;j++){ if((j>>i)&1) continue; c2[j]=(c2[j]+c2[j+(1<<i)])%mod; } } for(int i=1;i<=m;i++){ if(c[x[i]]!=c[y[i]]) ide.push_back(i); }int ec=ide.size(); int Ue=(1<<ec)-1; for(int i=0;i<=Ue;i++){ if(i){ int j=__builtin_ctz(i); S1[i]=S1[i-(1<<j)]; S2[i]=S2[i-(1<<j)]; int u=x[ide[j]],v=y[ide[j]]; if(c[u]) S2[i]|=(1<<rk[u]); else S1[i]|=(1<<rk[u]); if(c[v]) S2[i]|=(1<<rk[v]); else S1[i]|=(1<<rk[v]); }ans=(ans+1ll*c1[S1[i]]*c2[S2[i]])%mod; }ans=1ll*ans*p2[m]%mod; cout<<ans<<endl; } return 0; }