#include <bits/stdc++.h>
using namespace std;
int n, h, ans;
int f[2][31][31][31], g[2][31][31][31];
void update() {
  int v;
  for (int i = 1; i <= h; i++)
    for (int j = i; j <= h; j++)
      for (int k = j; k <= h; k++)
        if (v = g[1][i][j][k]) {
          (f[1][(i + 1) < (h) ? (i + 1) : (h)][(j + 1) < (h) ? (j + 1) : (h)]
            [(k + 1) < (h) ? (k + 1) : (h)] += v) %= 1000000009;
          if (i < h)
            (f[1][1][(h) < (j + 1) ? (h) : (j + 1)]
              [(h) < (k + 1) ? (h) : (k + 1)] += v) %= 1000000009;
          else
            (f[0][1][(h) < (j + 1) ? (h) : (j + 1)]
              [(h) < (k + 1) ? (h) : (k + 1)] += v) %= 1000000009;
          if (j < h)
            (f[1][1][(h) < (i + 1) ? (h) : (i + 1)]
              [(h) < (k + 1) ? (h) : (k + 1)] += v) %= 1000000009;
          else
            (f[0][1][(h) < (i + 1) ? (h) : (i + 1)]
              [(h) < (k + 1) ? (h) : (k + 1)] += v) %= 1000000009;
          if (k < h)
            (f[1][1][(h) < (i + 1) ? (h) : (i + 1)]
              [(h) < (j + 1) ? (h) : (j + 1)] += v) %= 1000000009;
          else
            (f[0][1][(h) < (i + 1) ? (h) : (i + 1)]
              [(h) < (j + 1) ? (h) : (j + 1)] += v) %= 1000000009;
        }
  for (int i = 1; i <= h; i++)
    for (int j = i; j <= h; j++)
      for (int k = j; k <= h; k++)
        if (v = g[0][i][j][k]) {
          (f[0][(i + 1) < (h) ? (i + 1) : (h)][(j + 1) < (h) ? (j + 1) : (h)]
            [(k + 1) < (h) ? (k + 1) : (h)] += v) %= 1000000009;
          if (i < h)
            (f[1][(h) < (j + 1) ? (h) : (j + 1)][(h) < (k + 1) ? (h) : (k + 1)]
              [h] += v) %= 1000000009;
          else
            (f[0][(h) < (j + 1) ? (h) : (j + 1)][(h) < (k + 1) ? (h) : (k + 1)]
              [h] += v) %= 1000000009;
          if (j < h)
            (f[1][(h) < (i + 1) ? (h) : (i + 1)][(h) < (k + 1) ? (h) : (k + 1)]
              [h] += v) %= 1000000009;
          else
            (f[0][(h) < (i + 1) ? (h) : (i + 1)][(h) < (k + 1) ? (h) : (k + 1)]
              [h] += v) %= 1000000009;
          if (k < h)
            (f[1][(h) < (i + 1) ? (h) : (i + 1)][(h) < (j + 1) ? (h) : (j + 1)]
              [h] += v) %= 1000000009;
          else
            (f[0][(h) < (i + 1) ? (h) : (i + 1)][(h) < (j + 1) ? (h) : (j + 1)]
              [h] += v) %= 1000000009;
        }
}
int main() {
  cin >> n >> h;
  for (int i = 0; i < 4; i++) f[1][1][1][1] = 4;
  for (int i = 2; i <= n; i++) {
    memcpy(g, f, sizeof(g));
    memset(f, 0, sizeof(f));
    update();
  }
  for (int j = 1; j <= h; j++)
    for (int k = j; k <= h; k++)
      for (int t = k; t <= h; t++) {
        ans = (ans + f[1][j][k][t]) % 1000000009;
        if (j < h || k < h || t < h) ans = (ans + f[0][j][k][t]) % 1000000009;
      }
  printf("%d\n", ans);
}
