#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000009;
int n, h;
long long res;
int dp[1002][31][31][31][2];
long long p[1001];
inline void add(int& ret, int val) {
  ret += val;
  ret >= MOD && (ret -= MOD);
}
void gao(int i, int j, int k, int l) {
  int nj = max(0, j - 1);
  int nk = max(0, k - 1);
  int nl = max(0, l - 1);
  if (dp[i][j][k][l][0] != 0) {
    add(dp[i + 1][nj][nk][nl][0], dp[i][j][k][l][0]);
    add(dp[i + 1][nk][nl][0][j != 0 ? 1 : 0], dp[i][j][k][l][0]);
    add(dp[i + 1][nj][nl][0][k != 0 ? 1 : 0], dp[i][j][k][l][0]);
    add(dp[i + 1][nj][nk][0][l != 0 ? 1 : 0], dp[i][j][k][l][0]);
  }
  if (i >= n - h + 1) {
    res = (res + dp[i][j][k][l][1] * p[n - i]) % MOD;
  } else if (dp[i][j][k][l][1] != 0) {
    add(dp[i + 1][nj][nk][nl][1], dp[i][j][k][l][1]);
    add(dp[i + 1][h - 1][nk][nl][i + 1 <= h || j != 0 ? 1 : 0],
        dp[i][j][k][l][1]);
    add(dp[i + 1][h - 1][nj][nl][i + 1 <= h || k != 0 ? 1 : 0],
        dp[i][j][k][l][1]);
    add(dp[i + 1][h - 1][nj][nk][i + 1 <= h || l != 0 ? 1 : 0],
        dp[i][j][k][l][1]);
  }
}
int main() {
  for (int i = p[0] = 1; i <= 1000; ++i) {
    p[i] = p[i - 1] * 4 % MOD;
  }
  scanf("%d%d", &n, &h);
  memset(dp, 0, sizeof(dp));
  dp[1][0][0][0][1] = 4;
  res = 0;
  for (int i = 1; i <= n; ++i) {
    gao(i, 0, 0, 0);
    for (int j = 1; j < h; ++j) {
      gao(i, j, 0, 0);
      for (int k = 1; k < j; ++k) {
        gao(i, j, k, 0);
        for (int l = 1; l < k; ++l) {
          gao(i, j, k, l);
        }
      }
    }
  }
  printf("%I64d\n", res);
  return 0;
}
