#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 9;
int add(int a, int b) { return a + b < mod ? a + b : a + b - mod; }
void add_self(int &a, int b) {
  a += b;
  if (a >= mod) a -= mod;
}
int n, h;
int dp[2][35][35][35][2];
int &get(int i, int a, int b, int c, int j) {
  return dp[i][min(a, h)][min(b, h)][min(c, h)][j];
}
int main() {
  scanf("%d %d", &n, &h);
  for (int a = 0; a <= h; a++)
    for (int b = 0; b <= h; b++) {
      for (int c = 0; c <= h; c++) {
        for (int j = 0; j < 2; j++) {
          dp[0][a][b][c][j] = j == 0 or a < h or b < h or c < h;
        }
      }
    }
  for (int i = 1; i <= n; i++) {
    int ii = i % 2;
    for (int a = 0; a <= h; a++)
      for (int b = 0; b <= h; b++)
        for (int c = 0; c <= h; c++) {
          for (int j = 0; j < 2; j++) {
            get(ii, a, b, c, j) = get(1 - ii, a + 1, b + 1, c + 1, j);
          }
        }
    for (int a = 0; a <= h; a++)
      for (int b = 0; b <= h; b++)
        for (int c = 0; c <= h; c++) {
          for (int j = 0; j < 2; j++) {
            int me = j == 0 ? 1 : h;
            int &ans = dp[ii][a][b][c][j];
            add_self(ans, get(1 - ii, me, b + 1, c + 1, a == h));
            add_self(ans, get(1 - ii, me, a + 1, c + 1, b == h));
            add_self(ans, get(1 - ii, me, a + 1, b + 1, c == h));
          }
        }
  }
  int ans = 0;
  for (int q = 0; q < 4; q++) {
    add_self(ans, dp[1 - n % 2][1][1][1][0]);
  }
  printf("%d\n", ans);
}
