#include <bits/stdc++.h>
using namespace std;
template <class T>
inline T min(T &a, T &b) {
  return a < b ? a : b;
}
template <class T>
inline T max(T &a, T &b) {
  return a > b ? a : b;
}
template <class T>
void read(T &x) {
  char ch;
  while ((ch = getchar()) && !isdigit(ch))
    ;
  x = ch - '0';
  while ((ch = getchar()) && isdigit(ch)) x = x * 10 + ch - '0';
}
struct point {
  int x, y;
  point() {}
  point(int _x, int _y) : x(_x), y(_y) {}
};
const int Mod = 1000000009;
int n, h;
int dp[1010][31][31][31][2], ans;
void add(int &a, int b) { a = (a + b) % Mod; }
int main() {
  scanf("%d%d", &n, &h);
  dp[0][h][h][h][1] = 1;
  for (int i = 0; i <= n - 1; i++)
    for (int p1 = 0; p1 <= h; p1++)
      for (int p2 = 0; p2 <= h; p2++)
        for (int p3 = 0; p3 <= h; p3++)
          for (int p4 = 0; p4 <= 1; p4++)
            if (dp[i][p1][p2][p3]) {
              add(dp[i + 1][p4 ? h : 0][max(p2 - 1, 0)][max(p3 - 1, 0)][p1 > 1],
                  dp[i][p1][p2][p3][p4]);
              add(dp[i + 1][max(p1 - 1, 0)][p4 ? h : 0][max(p3 - 1, 0)][p2 > 1],
                  dp[i][p1][p2][p3][p4]);
              add(dp[i + 1][max(p1 - 1, 0)][max(p2 - 1, 0)][p4 ? h : 0][p3 > 1],
                  dp[i][p1][p2][p3][p4]);
              add(dp[i + 1][max(p1 - 1, 0)][max(p2 - 1, 0)][max(p3 - 1, 0)][p4],
                  dp[i][p1][p2][p3][p4]);
            }
  for (int p1 = 0; p1 <= h; p1++)
    for (int p2 = 0; p2 <= h; p2++)
      for (int p3 = 0; p3 <= h; p3++)
        for (int p4 = 0; p4 <= 1; p4++)
          if (p1 || p2 || p3 || p4) add(ans, dp[n][p1][p2][p3][p4]);
  printf("%d\n", ans);
}
