#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
long long mod = 1e9 + 7;
long long n,m,ans,u,v;
long long f[1000001];
long long ksm(long long b,long long a)
{
	long long r = 1;
	while(a)
	{
		if(a % 2)
		  r = r * b % mod;
		b = b * b % mod;
		a /= 2;
	}
	return r;
}
int main()
{
	freopen("barrack.in","r",stdin);
	freopen("barrack.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
	{
	  scanf("%lld%lld",&u,&v);
	}
	ans = (n * ksm(2,m) % mod) % mod;
//	if(n <= 8)
//	{
//	}
//	else
//	{
		f[1] = 1;
		f[2] = 5;
		f[3] = 18;
		for(int i=4;i<=n;i++)
		  f[n]=4*f[n-1]%mod-4*f[n-2]%mod+ksm(2,n-2);
		printf("%lld",f[n] % mod);
//	}
//	}
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}
//bool operator * (node a,node b)
//{
//	return a < b;
//}