#include<bits/stdc++.h>
using namespace std;
//#define int long long
typedef long long ll;
const ll maxN=1e7,N=1e7+10,mod=1e9+9;
ll qpow(ll a,ll b){
	ll ans=1,base=a;
	while(b){
		if(b&1)	ans=ans*base%mod;
		base=base*base%mod;
		b>>=1;
	}
	return a;
}
ll T,n,k,inv[N]={0,1},fac[N]={1};
signed main(){
	scanf("%lld",&T);
	for(int i=1;i<=maxN;i++){
		fac[i]=fac[i-1]*i%mod;
	}
	for(int i=2;i<=maxN;i++){
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	}
	for(int i=2;i<=maxN;i++){
		inv[i]=(inv[i-1]+inv[i])%mod;
	}
	while(T--){
		scanf("%lld %lld",&n,&k);
		ll ans=(inv[n-1]-inv[k-1]+mod)%mod;
		if(k!=1)	ans++;
		printf("%lld\n",ans*fac[n-1]%mod);
	}
	return 0;
}
/*
exSample:

*/

这样一份代码交上去会显示

g++: 编译器内部错误：File size limit exceeded signal terminated program as 请提交一份完整的错误报告， 如有可能请附上经预处理后的源文件。 参阅 https://gcc.gnu.org/bugs/ 以获取指示。

但是我不知道为什么两个1e7的数组会导致MLE？