POWER C++

#include <bits/stdc++.h>
using namespace std;
long long t,a,n,s,m=1000000009;
long long lt(long long a, long long n) 
{
    if (n == 0) return 1;
    long long t = lt(a, n/2);
    t = ((t % m) * (t % m)) % m;
    if (n % 2 == 0) return t;
    return ((t % m) * (a % m)) % m;
}
int main()
{
   freopen("POWER.inp","r",stdin);
   freopen("POWER.out","w",stdout);
   scanf("%lld",&t);
   for(int i = 1; i <= t ; i++)
   {
       scanf("%lld%lld",&a,&n);
       s=lt(a,n);
       printf("%lld\n",s);
   }
}