/* Code by
__ __ __
/\ \__ /\ \ /\ \
__ _ __\ \ ,_\ \ \ \___ __ ___\ \ \/'\
/'__`\ /\`'__\ \ \/ \ \ _ `\ /'__`\ /'___\ \ , <
/\ \L\.\_\ \ \/ \ \ \_ \ \ \ \ \/\ \L\.\_/\ \__/\ \ \`\
\ \__/.\_\ \_\ \ \__\ \ \_\ \_\ \__/.\_\ \____\ \_\ \_\
\/__/\/_/ \/_/ \/__/ _______\/_/\/_/\/__/\/_/\/____/ \/_/\/_/
/\______\
\/______/
*/
#include "bits/stdc++.h"
using namespace std;
#define max(a, b) (a < b? b : a)
#define min(a, b) ((a>b)?b:a)
#define mod 1e9+7
#define FOR(a,c) for ( int (a)=0; (a)<(c); (a)++)
#define FORL(a,b,c) for ( int (a)=(b); (a)<=(c); (a)++)
#define FORR(a,b,c) for ( int (a)=(b); (a)>=(c); (a)--)
#define INF 1000000000000000003
typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
#define F first
#define S second
#define PB push_back
#define POB pop_back
#define MP make_pair
#define MOD 1000000007
ll k=2;
vector<ll> b; // b is base case
vector<vector<ll> > multiply(vector<vector<ll> > A,vector<vector<ll> > B ){
vector<vector<ll> > C(k,vector<ll>(k,0));
FOR(i,k)
FOR(j,k)
FOR(x,k)
C[i][j] = ((C[i][j]%MOD) + ((A[i][x]%MOD)*(B[x][j]%MOD))%MOD)%MOD;
return C;
}
vector<vector<ll> > pow(vector<vector<ll> > A,ll p){
if(p==1)
return A;
if(p%2==1)
return multiply(A, pow(A,p-1));
else{
vector<vector<ll> > X = pow(A,p/2);
return multiply(X,X);
}
}
ll compute(ll n,ll m){
//Suppose n<=k
if(n<=k){
return b[k-n];
}
//2. Transformation matrix
vector<vector<ll> > T{
{(m-1),(m-1)},
{1,0}
};
// 3. T^n-k
T = pow(T,n-k);
// 4. multiply by initial vector
ll res = 0;
FOR(i,k)
res = (res%MOD + ((T[0][i]%MOD)*(b[i]%MOD))%MOD)%MOD;
return res;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin>>T;
while(T--){
ll N,M;
cin>>N>>M;
if(M==1 && N>1)
cout<<0<<endl;
else if(M==1 && N==1)
cout<<1<<endl;
else{
b.PB((((M%MOD)*(M%MOD))%MOD));
b.PB((M%MOD));
cout<<compute(N,M)<<endl;
b.clear();
}
}
return 0;
}