#include <bits/stdc++.h>
#define inf 1000000000
#define M 1000000007
using namespace std;
const int N=5009181;
int n,m,dist[N],dep[N];
vector<int> g[N];
struct nd{
	int id,dis;
	operator <(const nd&x)const{return x.dis<dis;}
};
priority_queue<nd> p;
bool vis[N];
void dij(int s){
	for(int i=0;i<=n;++i){
		vis[i]=0;
		dist[i]=inf;
		dep[i]=0;
	}
	int x,v;
	vis[s]=1;
	dist[s]=0;
	p.push((nd){s,0});
	while(!p.empty()){
		x=p.top().id;
		p.pop();
		for(int i=0;i<(int)g[x].size();++i){
			v=g[x][i];
			if(dist[v]>dist[x]+1){
				dist[v]=dist[x]+1;
				if(vis[v]==0){
					p.push((nd){v,dist[v]});
					vis[v]=1;
				}
			}
		}
		
	}
} 
long long qsm(long long d,long long z){
	if(z==0)return 1;
	long long res=1;
	while(z){
		if(z%2==1){
			res=res*d%M;
		}
		d=d*d%M;
		z>>=1;
	}
	return res%M;
}
long long c[109817];
int main(){
	freopen("barrack.in","r",stdin);
	freopen("barrack.out","w",stdout);
	scanf("%d%d",&n,&m);
	long long ans=qsm(2*1ll,(long long)m)*1ll*n%M;
	cout<<ans<<endl;
	if(n<=30){
		int uu,vv;
		for(int i=1;i<=m;++i){
			scanf("%d%d",&uu,&vv);
			g[uu].push_back(vv),g[vv].push_back(uu);
		}	
		for(int i=1;i<=n;++i){
			dij(i);
			for(int j=1;j<=n;++j){
				if(j>=i)dep[dist[j]]++;
			}
			for(int j=1;j<=n;++j){
				if(dep[j]!=0){
					ans=ans+qsm(2,(long long)(m-j))%M*1ll*dep[j]%M;
					ans%=M;
				}
			}
		}
		printf("%lld\n",ans);
	}
	else {
		c[1]=1ll;
		for(int i=2;i<=n;++i){
			c[i]=c[i-1]*i%M;
		}
		ans=0;
		long long u=n;
		printf("%lld\n",c[n/2]*qsm(2,m/2+1)%M);
	}
	return 0;
}