#include <bits/stdc++.h>
int modint(int a, int b) {
  return (((a) >= 0) ? ((a) - (b) * ((a) / (b)))
                     : ((a) - (b) * ((a) / (b) + 1)));
}
long long modll(long long a, long long b) {
  return (((a) >= 0) ? ((a) - (b) * ((a) / (b)))
                     : ((a) - (b) * ((a) / (b) + 1)));
}
void fileio_in_out() {
  freopen(".in", "r", stdin);
  freopen(".out", "w", stdout);
}
void fileio_txt() {
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
}
int n, h, x, y, z, ww, xx, yy, zz;
int i, j, k, l;
long long dp[33][33][33][2][2], ans = 0, t;
int main() {
  scanf("%d%d", &n, &h);
  memset(dp, 0, sizeof(dp));
  dp[0][0][0][0][1] = 1;
  for (k = 0; k < n; k++)
    for (x = 0; x <= h; x++)
      for (y = 0; y <= h; y++)
        for (z = 0; z <= h; z++)
          for (j = 0; j <= 1; j++) {
            i = k % 2;
            t = dp[x][y][z][i][j];
            t = modll(t, ((1e9) + 9));
            dp[x][y][z][i][j] = 0;
            i ^= 1;
            xx = (((x + 1) < (h)) ? (x + 1) : (h));
            yy = (((y + 1) < (h)) ? (y + 1) : (h));
            zz = (((z + 1) < (h)) ? (z + 1) : (h));
            ww = j ? 1 : h;
            dp[xx][yy][zz][i][j] += t;
            dp[yy][zz][ww][i][(x < h)] += t;
            dp[xx][zz][ww][i][(y < h)] += t;
            dp[xx][yy][ww][i][(z < h)] += t;
          }
  i = n % 2;
  for (x = 0; x <= h; x++)
    for (y = 0; y <= h; y++)
      for (z = 0; z <= h; z++)
        for (j = 0; j <= 1; j++)
          if (x < h || y < h || z < h || j) {
            ans += dp[x][y][z][i][j];
            ans = modll(ans, ((1e9) + 9));
          }
  printf("%I64d\n", ans);
  return 0;
}
