#include <bits/stdc++.h>
using namespace std;
int n, m;
const long long mod = 1e9 + 9;
int main() {
  scanf("%d%d", &n, &m);
  if (m <= 20) {
    long long ret = 1;
    for (int j = 1; j <= n; j++) ret = ret * ((1 << m) - j) % mod;
    cout << ret << endl;
    return 0;
  }
  long long k = 1, ret = 1;
  for (int i = 1; i <= m; i++) k = k * 2 % mod;
  for (int j = 1; j <= n; j++) ret = ret * (k - j) % mod;
  cout << ret << endl;
  return 0;
}
