#include <bits/stdc++.h>
const int inf = (1ll << 31) - 1;
const int maxn = (int)1e5 + 10;
using namespace std;
int mod = 1000000009;
int n, h;
int dp[3][31][31][31][2];
bool used[1001][31][31][31][2];
int nxt[35];
void add(int &v, int r) {
  v += r;
  if (v >= mod) v -= mod;
}
inline int get(int pos, int l1, int l2, int l3, bool ok) {
  return dp[pos][l1][l2][l3][ok];
}
int main() {
  cin >> n >> h;
  int prev = 0;
  int cur = 1;
  for (int i = 0; i <= h; i++) {
    for (int j = i; j <= h; j++)
      for (int k = j; k <= h; k++)
        for (int t = 0; t < 2; t++)
          if (t || i < h) dp[prev][k][j][i][t] = 1;
  }
  for (int i = 0; i <= h + 1; i++) nxt[i] = min(i + 1, h);
  for (int pos = n - 1; pos >= 0; pos--) {
    for (int i = 0; i <= h; i++)
      for (int j = i; j <= h; j++)
        for (int k = j; k <= h; k++) {
          add(dp[cur][k][j][i][1], dp[prev][nxt[k]][nxt[j]][nxt[i]][1]);
          add(dp[cur][k][j][i][1], dp[prev][nxt[k]][nxt[j]][1][i < h]);
          add(dp[cur][k][j][i][1], dp[prev][nxt[k]][nxt[i]][1][j < h]);
          add(dp[cur][k][j][i][1], dp[prev][nxt[j]][nxt[i]][1][k < h]);
          add(dp[cur][k][j][i][0], dp[prev][nxt[k]][nxt[j]][nxt[i]][0]);
          add(dp[cur][k][j][i][0], dp[prev][h][nxt[k]][nxt[j]][i < h]);
          add(dp[cur][k][j][i][0], dp[prev][h][nxt[k]][nxt[i]][j < h]);
          add(dp[cur][k][j][i][0], dp[prev][h][nxt[j]][nxt[i]][k < h]);
        }
    swap(prev, cur);
    for (int i = 0; i <= h; i++)
      for (int j = i; j <= h; j++)
        for (int k = j; k <= h; k++) {
          dp[cur][k][j][i][1] = 0;
          dp[cur][k][j][i][0] = 0;
        }
  }
  cout << dp[prev][0][0][0][1] << endl;
  return 0;
}
