#include<iostream>
#include<vector>
#include<algorithm>

//#define int long long
#define endl '\n'
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define x first
#define y second
#define lc root<<1
#define rc root<<1|1
const int N = 1e5+2;
using namespace std;
using PII = pair<int,int>;
using i128 = __int128;
#define debug0
const int MOD = 1e9+9;
int qpow(int x,int n){
    int ans = 1;
    while(n){
        if(n & 1)ans = (1ll * ans * x) % MOD;
        x = (1ll * x * x) % MOD;
        n >>= 1;
    }
    return ans;
}


void solve(){
    int m,k;cin >> m >> k;
    int s = 0,ls = 0,lp = 1,Eld = 0;
    int ppp = (5ll * qpow(3,MOD-2)) % MOD;
//    cout << (666666673ll * 3 / 5) % MOD << endl;
    for(int i = 1;i <= k;++i){
        s = (1ll * m * (Eld+1) % MOD + s) % MOD;
        ls = ( (MOD + ls - Eld) % MOD + 1ll * m * (Eld + 1) % MOD) % MOD;
        lp = (lp - 1 + m) % MOD;
        Eld = 1ll * ls * qpow(lp,MOD-2) % MOD;
//        double dEld = 1.0 * MOD / (double)Eld;
//        cout << s << " " << p << " " << ls << " " << lp << " " << Eld << " " << dEld << endl;
    }
    cout << s << endl;
}



#define FILE
#define MULTI0
int main(){
#ifndef ONLINE_JUDGE
#ifdef FILE
    freopen("in.txt", "r",stdin);
    freopen("out.txt", "w",stdout);
#endif
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;

#ifdef MULTI
    cin >> T;
#endif

    while (T--) {
        solve();
    }
    return 0;
}