#include <cstdio> #include <cstring> #include <algorithm> long long s=723398404,r1=308495997,r2=691504013; long long mod=1000000009; long long c[100005]; typedef long long Ma[2][2]; void egcd(long long a,long long b,long long &x,long long &y) { if (b==0) { x=1; y=0; return; } egcd(b,a%b,x,y); int t=x; x=y,y=t-a/b*y; return; } long long mypow(long long x,long long y) { long long res=1; while (y) { if (y%2) res=res * x % mod; x=x * x % mod; y/=2; } return res; } long long acce(long long x,long long y) { long long ans=0; long long powe=x; long long sum=x; long long mul=1; while (y) { if (y&1) { ans+=mul*sum; ans%=mod; mul*=powe; mul%=mod; } sum*=(powe+1); sum%=mod; powe*=powe; powe%=mod; y/=2; } return ans; } int main() { int T; long long n,m; scanf("%d",&T); while (T--) { long long ans=0; scanf("%lld%lld",&n,&m); c[0]=1; long long x,y; for (long long i=1;i<=m;i++) { egcd(i,mod,x,y); x=(x+mod)%mod; c[i]=(c[i-1]*x)%mod; c[i]=(c[i]*(m-i+1))%mod; } for (long long i=0;i<=m;i++) { x=c[i]; x=x * acce(mypow(r1,i)*mypow(r2,m-i)%mod,n)%mod; x=(x+mod)%mod; if ((m-i)%2) ans=(ans - x + mod)%mod; else ans=(ans + x + mod)%mod; } ans=ans*mypow(s,m)%mod; printf("%lldn",ans); } return 0; }
