#include<bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7, KMAX = 1e6 + 5;
long long n, k, fact[KMAX];

long long ridput(long long x, long long y)
{
	long long p = 1;
	
	x = x % MOD;
	
	while(y > 0)
	{
		if(y & 1)
		{
			p *= x;
			p %= MOD;
		}	
		
		y >>= 1;
		
		x = (x * x) % MOD;
	}
	
	return p;
}

void query()
{
	cin >> n >> k;

	long long prim = ridput(fact[k], n / k);
	
	long long fact_sec = 1;

	
	fact_sec = ((fact[k] * ridput(n % k, MOD - 2)) % MOD * ridput(k - n % k, MOD - 2)) % MOD;	
	cout <<  (prim * fact_sec) % MOD << "\n";
	
}

int main()
{
	freopen("cabana.in", "r", stdin);
	fsreopen("cabana.out", "w", stdout);

	fact[0] = 1;
	for(int i = 1; i <= KMAX; i++)
	{
		fact[i] = fact[i - 1] * i;
		fact[i] %= MOD;
	}

	int t;
	cin >> t;
	
	while(t--)
		query();
}