#include <bits/stdc++.h>
#pragma GCC optimize(3)
namespace orz {
inline void read(int &x) { scanf("%d", &x); }
inline void read(unsigned int &x) { scanf("%u", &x); }
inline void read(long long &x) { scanf("%I64d", &x); }
inline void read(unsigned long long &x) { scanf("%I64u", &x); }
inline void read(double &x) { scanf("%lf", &x); }
inline void read(long double &x) {
  double tmp;
  read(tmp);
  x = tmp;
}
inline void read(char &x) { x = getchar(); }
inline void read(char *x) { scanf("%s", x); }
template <class T>
inline void read(T *a, int n) {
  for (int i = (0); i < (n); ++i) read(a[i]);
}
template <class T1, class T2>
inline void read(T1 &a, T2 &b) {
  read(a);
  read(b);
}
template <class T1, class T2, class T3>
inline void read(T1 &a, T2 &b, T3 &c) {
  read(a);
  read(b);
  read(c);
}
template <class T1, class T2, class T3, class T4>
inline void read(T1 &a, T2 &b, T3 &c, T4 &d) {
  read(a);
  read(b);
  read(c);
  read(d);
}
template <class T1, class T2, class T3, class T4, class T5>
inline void read(T1 &a, T2 &b, T3 &c, T4 &d, T5 &e) {
  read(a);
  read(b);
  read(c);
  read(d);
  read(e);
}
inline void write(int x) { printf("%d", x); }
inline void write(unsigned int x) { printf("%u", x); }
inline void write(long long x) { printf("%I64d", x); }
inline void write(unsigned long long x) { printf("%I64u", x); }
inline void write(double x) { printf("%.10lf", x); }
inline void write(long double x) { printf("%.10lf", (double)x); }
inline void write(char x) { putchar(x); }
inline void write(char *x) { printf("%s", x); }
template <class T>
inline void writes(T x) {
  write(x);
  putchar(' ');
}
template <class T1, class T2>
inline void writes(T1 a, T2 b) {
  writes(a);
  writes(b);
}
template <class T1, class T2, class T3>
inline void writes(T1 a, T2 b, T3 c) {
  writes(a);
  writes(b);
  writes(c);
}
template <class T1, class T2, class T3, class T4>
inline void writes(T1 a, T2 b, T3 c, T4 d) {
  writes(a);
  writes(b);
  writes(c);
  writes(d);
}
template <class T1, class T2, class T3, class T4, class T5>
inline void writes(T1 a, T2 b, T3 c, T4 d, T5 e) {
  writes(a);
  writes(b);
  writes(c);
  writes(d);
  writes(e);
}
template <class T1, class T2>
inline void writesln(T1 a, T2 b) {
  writes(a);
  writes(b);
  putchar('\n');
}
template <class T1, class T2, class T3>
inline void writesln(T1 a, T2 b, T3 c) {
  writes(a);
  writes(b);
  writes(c);
  putchar('\n');
}
template <class T1, class T2, class T3, class T4>
inline void writesln(T1 a, T2 b, T3 c, T4 d) {
  writes(a);
  writes(b);
  writes(c);
  writes(d);
  putchar('\n');
}
template <class T1, class T2, class T3, class T4, class T5>
inline void writesln(T1 a, T2 b, T3 c, T4 d, T5 e) {
  writes(a);
  writes(b);
  writes(c);
  writes(d);
  writes(e);
  putchar('\n');
}
template <class T1, class T2>
inline void writeln(T1 a, T2 b) {
  write(a);
  write(b);
  putchar('\n');
}
template <class T1, class T2, class T3>
inline void writeln(T1 a, T2 b, T3 c) {
  write(a);
  write(b);
  write(c);
  putchar('\n');
}
template <class T1, class T2, class T3, class T4>
inline void writeln(T1 a, T2 b, T3 c, T4 d) {
  write(a);
  write(b);
  write(c);
  write(d);
  putchar('\n');
}
template <class T1, class T2, class T3, class T4, class T5>
inline void writeln(T1 a, T2 b, T3 c, T4 d, T5 e) {
  write(a);
  write(b);
  write(c);
  write(d);
  write(e);
  putchar('\n');
}
template <class T1, class T2>
inline void write(T1 a, T2 b) {
  write(a);
  write(b);
}
template <class T1, class T2, class T3>
inline void write(T1 a, T2 b, T3 c) {
  write(a);
  write(b);
  write(c);
}
template <class T1, class T2, class T3, class T4>
inline void write(T1 a, T2 b, T3 c, T4 d) {
  write(a);
  write(b);
  write(c);
  write(d);
}
template <class T1, class T2, class T3, class T4, class T5>
inline void write(T1 a, T2 b, T3 c, T4 d, T5 e) {
  write(a);
  write(b);
  write(c);
  write(d);
  write(e);
}
template <class T>
inline void writeln(T x) {
  write(x);
  putchar('\n');
}
template <class T>
inline void writeln(T *a, int n) {
  for (int i = (0); i < (n); ++i) write(a[i]);
  putchar('\n');
}
template <class T>
inline void writesln(T *a, int n) {
  for (int i = (0); i < (n); ++i) writes(a[i]);
  putchar('\n');
}
template <class T>
inline void writelnln(T *a, int n) {
  for (int i = (0); i < (n); ++i) writeln(a[i]);
}
}  // namespace orz
using namespace orz;
int n, h;
int dp[1001][2][31][31][31];
const int MOD = 1000000009;
int main() {
  read(n, h);
  --h;
  memset(dp, 0, sizeof(dp));
  dp[1][1][0][0][0] = 1;
  for (int i = (1); i < (n); ++i) {
    for (int i1 = (0); i1 <= (h); ++i1)
      for (int i2 = (i1); i2 <= (h); ++i2)
        for (int i3 = (i2); i3 <= (h); ++i3) {
          int c = dp[i][1][i1][i2][i3], ii1 = ((i1 ^ h) ? (i1 + 1) : i1),
              ii2 = ((i2 ^ h) ? (i2 + 1) : i2),
              ii3 = ((i3 ^ h) ? (i3 + 1) : i3);
          {
            int &tmp = dp[i + 1][1][ii1][ii2][ii3];
            if ((tmp += c) >= MOD) tmp -= MOD;
          }
          {
            int &tmp = dp[i + 1][i1 != h][0][ii2][ii3];
            if ((tmp += c) >= MOD) tmp -= MOD;
          }
          {
            int &tmp = dp[i + 1][i2 != h][0][ii1][ii3];
            if ((tmp += c) >= MOD) tmp -= MOD;
          }
          {
            int &tmp = dp[i + 1][i3 != h][0][ii1][ii2];
            if ((tmp += c) >= MOD) tmp -= MOD;
          }
        }
    for (int i1 = (0); i1 <= (h); ++i1)
      for (int i2 = (i1); i2 <= (h); ++i2)
        for (int i3 = (i2); i3 <= (h); ++i3) {
          int c = dp[i][0][i1][i2][i3], ii1 = ((i1 ^ h) ? (i1 + 1) : i1),
              ii2 = ((i2 ^ h) ? (i2 + 1) : i2),
              ii3 = ((i3 ^ h) ? (i3 + 1) : i3);
          {
            int &tmp = dp[i + 1][0][ii1][ii2][ii3];
            if ((tmp += c) >= MOD) tmp -= MOD;
          }
          {
            int &tmp = dp[i + 1][i1 != h][ii2][ii3][h];
            if ((tmp += c) >= MOD) tmp -= MOD;
          }
          {
            int &tmp = dp[i + 1][i2 != h][ii1][ii3][h];
            if ((tmp += c) >= MOD) tmp -= MOD;
          }
          {
            int &tmp = dp[i + 1][i3 != h][ii1][ii2][h];
            if ((tmp += c) >= MOD) tmp -= MOD;
          }
        }
  }
  int ans = 0;
  for (int al = (0); al <= (1); ++al)
    for (int i1 = (0); i1 <= (h); ++i1)
      for (int i2 = (i1); i2 <= (h); ++i2)
        for (int i3 = (i2); i3 <= (h); ++i3)
          if (al || i1 < h || i2 < h || i3 < h)
            (ans += dp[n][al][i1][i2][i3]) %= MOD;
  writeln(ans * 2 % MOD * 2 % MOD);
  return 0;
}
