#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

long power(long base, long exponent){
    if(exponent % 2){
        return power(base, exponent - 1) * base % long(1e9 + 9);
    }else if(exponent){
        long root_ans = power(base, exponent / 2);
        return root_ans * root_ans % long(1e9 + 9);
    }else{
        return 1;
    }
}

int main(){
    long N;
    int K;
    cin >> N >> K;
    long average_integer = ((1l << K) - 1) % long(1e9 + 9) * (1l << (K - 1)) % long(1e9 + 9) * N % long(1e9 + 9);
    cout << average_integer << endl;
}