1557C - Moamen and XOR - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int T;
ll n,k;
ll ksm(ll x,ll y){
	if(y==0) return 1; 
	ll tmp=1;
	while(y){
		if(y&1) tmp=(tmp*x)%mod;
		x=(x*x)%mod;
		y/=2; 
	}
	return tmp%mod;
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%lld%lld",&n,&k);
		ll ans=0,p=1;
		for(ll i=1;i<=k;++i){
			if(n%2==0){
				if(k==i) ans+=p;
				else ans=ans+(p*(ksm(ksm(2,k-i),n)))%mod;
				ans=ans%mod;
			}
			ll tmp;
			if(n%2) tmp=(ksm(2,n-1)+1)%mod;
			else tmp=(ksm(2,n-1)-1)%mod;
			p=(p*tmp)%mod;
		}
		ans=(ans+p)%mod;
		printf("%lld\n",ans);
	}
	return 0;
}