Cacher is the code snippet organizer for pro developers

#include <iostream>
using namespace std;

// #Theory #Math

long long fast_exp(long long base,long long exp){
    if(base==0){
        return 0;
    }
    long long MOD=10000009;
    long long result=1;
    while(exp>0){
        if(exp%2==1){
            result=(result*base)%MOD;
        }
        base=(base*base)%MOD;
        exp/=2;
    }
    return result%MOD;
}

int main() {
    cout<<fast_exp (2,5);
    return 0;
}