/* 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;
}

#include <iostream>

using namespace std;
using ll = long long;
#define N 1000000007
void mul(ll F[2][2], ll M[2][2]) 
{ 
  ll x =  (F[0][0]*M[0][0] + F[0][1]*M[1][0])%N; 
  ll y =  (F[0][0]*M[0][1] + F[0][1]*M[1][1])%N; 
  ll z =  (F[1][0]*M[0][0] + F[1][1]*M[1][0])%N; 
  ll w =  (F[1][0]*M[0][1] + F[1][1]*M[1][1])%N; 
  
  F[0][0] = x; 
  F[0][1] = y; 
  F[1][0] = z; 
  F[1][1] = w; 
} 
ll matmul(ll mat[2][2], ll n, ll m)
{
    ll ans[2][2];
    ans[0][0] = 1;
    ans[0][1] = 0;
    ans[1][0] = 0;
    ans[1][1] = 1;
    while(n > 0)
    {
        if(n%2 == 1)
            mul(ans, mat);
        n = n/2;
        mul(mat, mat);
    }
    ll x = (m*m)%N;
    return (ans[0][0]*x + ans[0][1]*m)%N;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        ll n, m;
        cin >> n >> m;
        m = m%N;
        ll mat[2][2];
        mat[0][0] = m-1;
        mat[0][1] = m-1;
        mat[1][0] = 1;
        mat[1][1] = 0;
        if(n == 1)
            cout << m << '\n';
        else if(n == 2)
            cout << (m*m)%N << '\n';
        else
            cout << (matmul(mat, n-2, m)+N)%N << '\n';
    }
}