const int MOD =  + ;

 const int maxn =  + ;

 LL C[maxn][maxn];

 LL inv[maxn];

 LL B[maxn];

 LL n, k;

 void init()

 {

     scanf("%lld%lld", &n, &k);

 }

 void getC()

 {

     C[][] = ;

     for(int i = ; i < maxn; i++) {

         C[i][] = C[i][i] = ;

         for(int j = ; j < i; j++)

             C[i][j] = (C[i-][j] + C[i-][j-]) % MOD;

     }

 }

 void getInv() //O(n) 求所有逆元

 {

     inv[] = ;

     for (int i = ; i < maxn; i++)

     {

         inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;

     }

 }

 void getB() //求伯努利数

 {

     B[] = ;

     for (int i = ; i < maxn - ; i++)

     {

         for (int j = ; j < i; j++)

         {

             B[i] = (B[i] + C[i+][j] * B[j]) % MOD;

         }

         B[i] = (-inv[i+] * B[i] % MOD + MOD) % MOD;

     }

 }

 LL ni[maxn];

 void solve()

 {

     n %= MOD; //1e18会爆

     ni[] = ;

     for (int i = ; i <= k + ; i++) ni[i] = ni[i-] * (n + ) % MOD;

     LL ans = ;

     for (int i = ; i <= k; i++)

     {

         ans = (ans + C[k+][i] * ni[k+-i] % MOD * B[i] % MOD) % MOD;

     }

     ans = ans * inv[k+] % MOD;

     printf("%lld\n", ans);

 }

 int main()

 {

     getInv();

     getC();

     getB();

     int T;

     scanf("%d", &T);

     while (T--)

     {

         init();

         solve();

     }

     return ;

 }