#include <bits/stdc++.h>
using namespace std;
template <class T>
void chmax(T& a, const T& b) {
  a = max(a, b);
}
template <class T>
void chmin(T& a, const T& b) {
  a = min(a, b);
}
template <class T>
void uniq(vector<T>& c) {
  sort(c.begin(), c.end());
  c.erase(unique(c.begin(), c.end()), c.end());
}
template <class T>
string to_s(const T& a) {
  ostringstream os;
  os << a;
  return os.str();
}
template <class T>
T to_T(const string& s) {
  istringstream is(s);
  T res;
  is >> res;
  return res;
}
template <class T, class U>
ostream& operator<<(ostream& os, pair<T, U>& p) {
  os << "( " << p.first << ", " << p.second << " )";
  return os;
}
template <class T>
void print(T a, int n, const string& deli = " ", int br = 1) {
  for (int i = 0; i < n; ++i) {
    cout << a[i];
    if (i + 1 != n) cout << deli;
  }
  while (br--) cout << endl;
}
template <class T>
void print(const T& c, const string& deli = " ", int br = 1) {
  for (__typeof__((c).begin()) it = (c).begin(); it != (c).end(); ++it) {
    cout << *it;
    if (++it != c.end()) cout << deli;
    --it;
  }
  while (br--) cout << endl;
}
template <class T>
void print2d(T a, int w, int h, int width = -1, int br = 1) {
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      if (width != -1) cout.width(width);
      cout << a[i][j] << ' ';
    }
    cout << endl;
  }
  while (br--) cout << endl;
}
template <class T>
void input(T& a, int n) {
  for (int i = 0; i < n; ++i) cin >> a[i];
}
template <class T>
void input(T* a, int n) {
  for (int i = 0; i < n; ++i) cin >> a[i];
}
void fix_pre(int n) {
  cout.setf(ios::fixed, ios::floatfield);
  cout.precision(10);
}
void fast_io() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}
bool in_rect(int x, int y, int w, int h) {
  return 0 <= x && x < w && 0 <= y && y < h;
}
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const double PI = acos(-1.0);
const int mod = ((long long)(1e9)) + 9;
int n, h;
void add(int& a, int b) {
  a += b;
  if (a >= mod) a -= mod;
}
int next_diff(int diff) { return (diff == 0 || diff == h - 1) ? 0 : diff + 1; }
int main() {
  cin >> n >> h;
  static int dp[1005][2][32][32][32];
  int ar = h == 1 ? 0 : 1;
  dp[1][1][ar][ar][ar] = 4;
  for (int height = 1; height < n; ++height)
    for (int alive = 0; alive < (int)(2); ++alive)
      for (int i = 0; i < (int)(h); ++i)
        for (int j = 0; j < (int)(h); ++j)
          for (int k = 0; k < (int)(h); ++k) {
            int cur = dp[height][alive][i][j][k];
            int nd = alive ? 1 : 0;
            int ni = next_diff(i);
            int nj = next_diff(j);
            int nk = next_diff(k);
            add(dp[height + 1][alive][ni][nj][nk], cur);
            add(dp[height + 1][i > 0][nd][nj][nk], cur);
            add(dp[height + 1][j > 0][nd][ni][nk], cur);
            add(dp[height + 1][k > 0][nd][ni][nj], cur);
          }
  int res = 0;
  for (int alive = 0; alive < (int)(2); ++alive)
    for (int i = 0; i < (int)(h); ++i)
      for (int j = 0; j < (int)(h); ++j)
        for (int k = 0; k < (int)(h); ++k)
          if (alive || i || j || k) add(res, dp[n][alive][i][j][k]);
  cout << res << endl;
}
