#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:268435456")
using namespace std;
const double PI = 3.1415926535897932384626433832795;
template <class T>
T min(T &a, T &b) {
  return (a < b) ? a : b;
}
template <class T>
T max(T &a, T &b) {
  return (a > b) ? a : b;
}
template <class T>
T sqr(T &a) {
  return a * a;
}
template <class T>
T abs(T &a) {
  return (a < 0) ? (-a) : a;
}
inline void read(int &x) { scanf("%d", &x); }
inline void readln(int &x) { scanf("%d\n", &x); }
inline void write(int x) { printf("%d", x); }
inline void writeln(int x) { printf("%d\n", x); }
inline void read(long long &x) { scanf("%lld", &x); }
inline void readln(long long &x) { scanf("%lld\n", &x); }
inline void write(long long x) { printf("%lld", x); }
inline void writeln(long long x) { printf("%lld\n", x); }
inline void read(double &x) { scanf("%lf", &x); }
inline void readln(double &x) { scanf("%lf\n", &x); }
inline void write(double x) { printf("%.15lf", x); }
inline void writeln(double x) { printf("%.15lf\n", x); }
inline void read(char *s) { scanf("%s", s); }
inline void readln(char *s) { scanf("%s\n", s); }
inline void write(char *s) { printf("%s", s); }
inline void writeln(char *s) { printf("%s\n", s); }
inline int readInt() {
  int x;
  read(x);
  return x;
}
inline long long readLong() {
  long long x;
  read(x);
  return x;
}
inline double readDouble() {
  double x;
  read(x);
  return x;
}
inline void showTime() {}
inline void prepareInputOutput() {}
int ans;
vector<int> v;
bool ok() {
  for (int L = 0; L < ((int)((v).size())); L++) {
    for (int R = L; R < ((int)((v).size())); R++) {
      int x = 0;
      for (int i = ((int)(L)); i <= ((int)(R)); i++) x ^= v[i];
      if (x == 0) return false;
    }
  }
  return true;
}
void rec(int curLen, int len, int maxVal) {
  if (curLen == len) {
    if (ok()) {
      ans++;
    }
    return;
  }
  for (int i = 0; i < ((int)(maxVal)); i++) {
    v.push_back(i);
    rec(curLen + 1, len, maxVal);
    v.pop_back();
  }
}
int f(int len, int bits) {
  ans = 0;
  v.clear();
  rec(0, len, 1 << bits);
  return ans;
}
vector<int> factorize(int x) {
  vector<int> v;
  int xx = x;
  for (int i = 2; i * i <= xx; i++) {
    while (x % i == 0) {
      v.push_back(i);
      x /= i;
    }
  }
  if (x != 1) v.push_back(x);
  sort((v).begin(), (v).end());
  return v;
}
const long long mod = 1000 * 1000 * 1000 + 9;
long long binpow(long long x, long long n) {
  if (n == 0) return 1;
  if (n % 2 == 0) {
    long long y = binpow(x, n / 2);
    return (y * y) % mod;
  }
  return (x * binpow(x, n - 1)) % mod;
}
long long solve(int len, int bits) {
  if (bits < 25) {
    if (len >= (1 << bits)) {
      return 0;
    }
  }
  long long ans = 1;
  for (int i = 1; i <= len; i++) {
    long long mult = binpow(2, bits);
    mult = (mult - i + mod) % mod;
    ans = (ans * mult) % mod;
  }
  return ans;
}
int main() {
  prepareInputOutput();
  int len, bits;
  cin >> len >> bits;
  cout << solve(len, bits);
  showTime();
}
