#include
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
long long int power (long long int t, long long int p) {
int64_t ans=1ll;
while§ {
if(p&1)ans=(anst)%MOD;
t=(tt)%MOD;
p=p/2;
}
return ans%1000000007;
}
int main()
{
int x;
cin>>x;
for(int i=0;i<x;i++)
{
int n,a;
cin>>n>>a;
int64_t prod=a*a,set=a*a,count=0;
int j=3;
for(int i=1;i<n;i++)
{
int64_t n1=prod;
set=prod;
int k=j-1;
int64_t an=power(n1,k);
set=(set%1000000007)*(an%1000000007);
j=j+2;
prod= (set%1000000007)*(prod%1000000007);
count+=set%1000000007;
}
cout<<(count+a)%1000000007<<'\n';
}
}