【快速幂】

#include 
#define mod 1000009
using namespace std;
int quickmod(int a,int b){
    int ans = 1;
    while(b > 0){
        if(b % 2 == 1){
            ans = ans * a % mod;
        }
        a = a * a % mod;
        b = b / 2;
    }
    return ans;
}
int main(){
    long long a,b;
    cin>>a>>b;
    cout<     return 0;
}