C3 in LOSH 2016

#include <iostream>

using namespace std;
const long long mod = 1000000009;

long long t(long long a, long long b){
    return (a * b)%mod;
}

long long bin_pow(long long a, long long n){
    if (n == 0){
        return 1;
    }
    if (n % 2 == 0){
        long long pp = bin_pow(a, n / 2);
        return t(pp, pp);
    } else{
        return t(a, bin_pow(a, n - 1));
    }
}

int main(){
    int n=0;
    cin >> n;
    long long y = mod-2;
    long long a[n];
    for (int i = 0;i  < n; i++)
        cin >> a[i];
    for (int i = 0;i  < n; i++)
        cout << bin_pow(a[i], y) <<'\n';

}