#include<cstdio>
typedef long long ll;
inline ll read(){
	ll x=0;
	int f=0,ch=0;
	while(ch<48||ch>57) f=(ch=='-'),ch=getchar();
	while(ch>47&&ch<58) x=(x<<3)+(x<<1)+(ch&15),ch=getchar();
	return f?-x:x;
}
inline void write(ll x,char end='\n'){
	if(x==0){
		putchar('0');
		putchar(end);
		return;
	}
	if(x<0) putchar('-'),x=-x;
	int ch[40]={0},cnt=0;
	while(x){
		ch[cnt++]=(int)(x%10);
		x/=10;
	}
	while(cnt--) putchar(ch[cnt]+48);
	putchar(end);
}
const ll mod=1e9+7;
ll n;
ll p;
inline ll fp(ll x,ll y){
	ll s=1;
	x=(x%mod+mod)%mod;
	while(y){
		if(y&1) s=s*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return s;
}
int main(){
	int T=read();
	while(T--){
		n=read(),p=read();
		if(n==0){
			write(0);
			continue;
		}
		if(n%2==0){
			write(15ll*(n/2+1)%mod);
			continue;
		}
		ll ans=15ll*(n/2+1)%mod;
		ll r=n/6;
		if(r>0){
			ll p1=1-fp(1-p,r);
			ll p2=1-fp(1-p,r)-fp(1-p,r-1)*p%mod*r%mod;
			p1=(p1%mod+mod)%mod;
			p2=(p2%mod+mod)%mod;
			ll s=1-(1-p1)*(1-p2)%mod;
			s=(s%mod+mod)%mod;
			ans+=s*(7*p1%mod+6*(1-p1)%mod*p2%mod+3*(1-p1)%mod*(p1-p2)%mod)%mod;
		}
		ans=(ans%mod+mod)%mod;
		write(ans);
	}
	return 0;
}