#include <bits/stdc++.h>
using namespace std;
int n, H, P = 1e9 + 9, f[2][31][31][31][2], ans, A;
void read(int &x) {
  char ch = getchar();
  int mark = 1;
  for (; ch != '-' && (ch < '0' || ch > '9'); ch = getchar())
    ;
  if (ch == '-') mark = -1, ch = getchar();
  for (x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - 48;
  x *= mark;
}
inline int max(const int &x, const int &y) { return (x > y) ? x : y; }
int main() {
  read(n);
  read(H);
  f[0][H][H][H][1] = 1;
  A = 0;
  for (int i = 1; i <= n; i++) {
    A ^= 1;
    memset(f[A], 0, sizeof(f[A]));
    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 < 2; p4++)
            if (f[A ^ 1][p1][p2][p3][p4]) {
              int now = f[A ^ 1][p1][p2][p3][p4];
              int New = p4 ? H : 0, P1 = max(p1 - 1, 0), P2 = max(p2 - 1, 0),
                  P3 = max(p3 - 1, 0);
              (f[A][New][P2][P3][p1 > 1] += now) %= P;
              (f[A][P1][New][P3][p2 > 1] += now) %= P;
              (f[A][P1][P2][New][p3 > 1] += now) %= P;
              (f[A][P1][P2][P3][p4] += now) %= P;
            }
  }
  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 < 2; p4++)
          if (p1 || p2 || p3 || p4) (ans += f[A][p1][p2][p3][p4]) %= P;
  printf("%d\n", ans);
  return 0;
}
