#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define pb push_back #define eb emplace_back #define ppc __builtin_popcountll using namespace std; typedef long long ll; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } const int mod=1e9+7; int n,m;int e[40][40];bool vis[40]; int cnt[40],deg[40],to[40],cc[40],toto[40]; int vis2[40]; int dp[40][2]; inline int pw(int x){return (1ll<<x)%mod;} int dfs(){ pi mx={-1,-1}; up(i,0,n-1)if(!vis[i]){ deg[i]=0,to[i]=0,cc[i]=0; up(j,0,n-1){deg[i]+=e[i][j];if(e[i][j])to[i]^=j,cc[i]++,toto[i]=j;} mx=max(mx,m_p(deg[i],i)); } if(mx.p1==-1)return 1; vector<int>nd; up(i,0,n-1)if(!vis[i])nd.eb(i); if(mx.p1<=2){ for(int i:nd)vis2[i]=0; auto work=[&](vector<int>v){ memset(dp,0,sizeof(dp)); dp[0][1]=pw(cnt[v[0]]); dp[0][0]=(pw(cnt[v[0]])-1)%mod; auto DP=[&](){ up(i,1,(int)v.size()-1){ dp[i][0]=(dp[i][0]+dp[i-1][1]*1ll*pw(cnt[v[i]]))%mod; dp[i][0]=(dp[i][0]+dp[i-1][0]*1ll*(pw(cnt[v[i]])-1))%mod; dp[i][1]=(dp[i][1]+dp[i-1][1]*1ll*pw(cnt[v[i]]))%mod; dp[i][1]=(dp[i][1]+dp[i-1][0]*1ll*pw(cnt[v[i]]))%mod; } }; DP();int res=dp[v.size()-1][0]; if((e[v[0]][v.back()]&&v.size()>2)||(v.size()==2&&e[v[0]][v[1]]>1)){ memset(dp,0,sizeof(dp)); dp[0][1]=dp[0][0]=pw(cnt[v[0]]); DP();res=(res+dp[v.size()-1][1])%mod; } return res; }; int res=1; for(int p:nd)if((!deg[p])&&(!vis2[p])) vis2[p]=1,res=res*1ll*(pw(cnt[p])-1)%mod; for(int p:nd)if(deg[p]==1&&(!vis2[p])){ vector<int>ve={p}; if(to[p]!=p){ int x=to[p],lst=p;ve={p,x}; while(deg[x]!=1){ int nx=to[x]^lst; lst=x,x=nx,ve.eb(nx); } } for(int u:ve)vis2[u]=1; res=res*1ll*work(ve)%mod; } for(int p:nd)if((!vis2[p])&&cc[p]==1){ vis2[p]=vis2[to[p]]=1; res=res*1ll*work({p,to[p]})%mod; } for(int p:nd)if(!vis2[p]){ int x=toto[p],lst=p; vector<int>ve={p,x}; while(x!=p){ int nx=to[x]^lst; lst=x,x=nx,ve.eb(nx); } ve.pop_back(); for(int u:ve)vis2[u]=1; res=res*1ll*work(ve)%mod; } return res; } int u=mx.p2; vector<int>tmp(n,0),tmpc(n,0); for(int i:nd)tmp[i]=e[i][u],tmpc[i]=cnt[i]; int res=pw(cnt[u]); for(int i:nd)e[i][u]=e[u][i]=0,cnt[i]+=tmp[i]; vis[u]=1;res=res*1ll*dfs()%mod; for(int i:nd)cnt[i]=tmpc[i]; res=(res+mod-dfs())%mod; for(int i:nd)e[i][u]=e[u][i]=tmp[i]; vis[u]=0; return res; } void slv(){ n=read(),m=read(); up(i,1,m){ int x=read(),y=read();x--,y--; if(x!=y)e[x][y]++,e[y][x]++; else cnt[x]++; } printf("%d\n",dfs()); } int main(){ //freopen("silksong.in","r",stdin),freopen("silksong.out","w",stdout); slv(); return 0; }