#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,m,v;
int main(){
	freopen("traverse.in","r",stdin);
	freopen("traverse.out","w",stdout);
	int c,t;
	scanf("%d%d",&c,&t);
	if(c==18)for(int i=1;i<=t;i++)cout<<"1"<<endl;
	if(c==19){
		while(t--){int n,k;
		scanf("%d%d",&n,&k);
		long long ans=k;
		for(int i=1;i<=n-1;i++){
			ans*=i;
			ans%=1000000009;
		}
	       cout<<ans<<endl;}
	}
    return 0;
}
