#include <bits/stdc++.h>
void read(int &x) {
  x = 0;
  int flag = 1;
  char ch = ' ';
  while (ch < '0' || ch > '9') {
    if (ch == '-') flag = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  x *= flag;
}
void read(long long &x) {
  x = 0;
  int flag = 1;
  char ch = ' ';
  while (ch < '0' || ch > '9') {
    if (ch == '-') flag = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  x *= flag;
}
using namespace std;
const int mod = 1e9 + 9, maxn = 1010;
void update(int &x, int y) {
  x += y;
  if (x >= mod) x -= mod;
}
int dp1[31][31][31][31], dp2[31][31][31][31], n, h;
int main() {
  read(n), read(h);
  dp1[0][0][0][0] = 1;
  for (int i = 1; i <= (int)n; i++) {
    for (int j = 0; j <= (int)h; j++)
      for (int k = 0; k <= (int)h; k++)
        for (int l = 0; l <= (int)h; l++)
          for (int r = 0; r <= (int)h; r++) {
            if (!dp1[j][k][l][r]) continue;
            update(dp2[j < h ? 0 : h][k < h ? k + 1 : h][l < h ? l + 1 : h]
                      [r < h ? r + 1 : h],
                   dp1[j][k][l][r]);
            update(dp2[j < h ? j + 1 : h][k < h ? 0 : h][l < h ? l + 1 : h]
                      [r < h ? r + 1 : h],
                   dp1[j][k][l][r]);
            update(dp2[j < h ? j + 1 : h][k < h ? k + 1 : h][l < h ? 0 : h]
                      [r < h ? r + 1 : h],
                   dp1[j][k][l][r]);
            update(dp2[j < h ? j + 1 : h][k < h ? k + 1 : h][l < h ? l + 1 : h]
                      [r < h ? 0 : h],
                   dp1[j][k][l][r]);
          }
    memcpy(dp1, dp2, sizeof(dp1));
    memset(dp2, 0, sizeof(dp2));
  }
  int ans = 0;
  for (int j = 0; j <= (int)h; j++)
    for (int k = 0; k <= (int)h; k++)
      for (int l = 0; l <= (int)h; l++)
        for (int r = 0; r <= (int)h; r++)
          if (j < h || k < h || l < h || r < h) update(ans, dp1[j][k][l][r]);
  printf("%d\n", ans);
  return 0;
}
