#include <bits/stdc++.h>
using namespace std;
const double pi = acos(0.0) * 2.0;
const double eps = 1e-12;
const int step[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <class T>
inline T max1(T a, T b) {
  return a > b ? a : b;
}
template <class T>
inline T min1(T a, T b) {
  return a < b ? a : b;
}
template <class T>
inline T gcd1(T a, T b) {
  if (a < b) swap(a, b);
  if (a % b == 0) return b;
  return gcd1(b, a % b);
}
template <class T>
inline T lb(T num) {
  return num & (-num);
}
inline int jud(double a, double b) {
  if (abs1(a - b) < eps) return 0;
  if (a < b) return -1;
  return 1;
}
template <class t>
inline int find(t val, t *a, int na, bool f_small = 1, bool f_lb = 1) {
  if (na == 1) return 0;
  int be = 0, en = na - 1;
  if (a[0] <= a[na - 1]) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(a[mid], val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(a[mid], val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(a[be], val) == 1 && be != 0) be--;
    if (!f_small && jud(a[be], val) == -1 && be != na - 1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(a[mid], val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(a[mid], val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(a[be], val) == -1 && be != 0) be--;
    if (f_small && jud(a[be], val) == 1 && be != na - 1) be++;
  }
  return be;
}
inline int bitnum(unsigned long long nValue) {
  nValue = ((0xaaaaaaaaaaaaaaaaull & nValue) >> 1) +
           (0x5555555555555555ull & nValue);
  nValue = ((0xccccccccccccccccull & nValue) >> 2) +
           (0x3333333333333333ull & nValue);
  nValue = ((0xf0f0f0f0f0f0f0f0ull & nValue) >> 4) +
           (0x0f0f0f0f0f0f0f0full & nValue);
  nValue = ((0xff00ff00ff00ff00ull & nValue) >> 8) +
           (0x00ff00ff00ff00ffull & nValue);
  nValue = ((0xffff0000ffff0000ull & nValue) >> 16) +
           (0x0000ffff0000ffffull & nValue);
  nValue = ((0xffffffff00000000ull & nValue) >> 32) +
           (0x00000000ffffffffull & nValue);
  return nValue;
}
long long pow(long long n, long long m, long long mod = 0) {
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
const int mod = 1000000009;
int n, h;
long long dp[2][32][32][32][32];
int a[4];
long long ans = 0, pp;
inline void trans(int now) {
  int nxt = 1 - now;
  dp[nxt][a[0] == h ? h : 0][min1(a[1] + 1, h)][min1(a[2] + 1, h)]
    [min1(a[3] + 1, h)] += dp[now][a[0]][a[1]][a[2]][a[3]];
  if (dp[nxt][a[0] == h ? h : 0][min1(a[1] + 1, h)][min1(a[2] + 1, h)]
        [min1(a[3] + 1, h)] > mod)
    dp[nxt][a[0] == h ? h : 0][min1(a[1] + 1, h)][min1(a[2] + 1, h)]
      [min1(a[3] + 1, h)] -= mod;
  dp[nxt][min1(a[0] + 1, h)][a[1] == h ? h : 0][min1(a[2] + 1, h)]
    [min1(a[3] + 1, h)] += dp[now][a[0]][a[1]][a[2]][a[3]];
  if (dp[nxt][min1(a[0] + 1, h)][a[1] == h ? h : 0][min1(a[2] + 1, h)]
        [min1(a[3] + 1, h)] > mod)
    dp[nxt][min1(a[0] + 1, h)][a[1] == h ? h : 0][min1(a[2] + 1, h)]
      [min1(a[3] + 1, h)] -= mod;
  dp[nxt][min1(a[0] + 1, h)][min1(a[1] + 1, h)][a[2] == h ? h : 0]
    [min1(a[3] + 1, h)] += dp[now][a[0]][a[1]][a[2]][a[3]];
  if (dp[nxt][min1(a[0] + 1, h)][min1(a[1] + 1, h)][a[2] == h ? h : 0]
        [min1(a[3] + 1, h)] > mod)
    dp[nxt][min1(a[0] + 1, h)][min1(a[1] + 1, h)][a[2] == h ? h : 0]
      [min1(a[3] + 1, h)] -= mod;
  dp[nxt][min1(a[0] + 1, h)][min1(a[1] + 1, h)][min1(a[2] + 1, h)]
    [a[3] == h ? h : 0] += dp[now][a[0]][a[1]][a[2]][a[3]];
  if (dp[nxt][min1(a[0] + 1, h)][min1(a[1] + 1, h)][min1(a[2] + 1, h)]
        [a[3] == h ? h : 0] > mod)
    dp[nxt][min1(a[0] + 1, h)][min1(a[1] + 1, h)][min1(a[2] + 1, h)]
      [a[3] == h ? h : 0] -= mod;
}
void dfs(int n, bool f, int now) {
  if (n == 3) {
    if (!f) {
      a[3] = 0;
      trans(now);
      a[3] = h;
      trans(now);
    } else
      for (int i = 0; i <= h; i++) {
        a[3] = i;
        trans(now);
      }
    return;
  }
  for (int i = 0; i < h + 1; i++) {
    a[n] = i;
    bool f1 = f | (i == 0 || i == h);
    dfs(n + 1, f1, now);
  }
}
void clr(int n, bool f, int now) {
  if (n == 3) {
    if (!f) {
      a[3] = 0;
      dp[1 - now][a[0]][a[1]][a[2]][a[3]] = 0;
      a[3] = h;
      dp[1 - now][a[0]][a[1]][a[2]][a[3]] = 0;
    } else
      for (int i = 0; i <= h; i++) {
        a[3] = i;
        dp[1 - now][a[0]][a[1]][a[2]][a[3]] = 0;
      }
    return;
  }
  for (int i = 0; i < h + 1; i++) {
    a[n] = i;
    bool f1 = f | (i == 0 || i == h);
    clr(n + 1, f1, now);
  }
}
void dfs2(int n, bool f, int now) {
  if (n == 3) {
    if (!f) {
      a[3] = 0;
      ans += (dp[now][a[0]][a[1]][a[2]][a[3]] * pp) % mod;
      if (ans > mod) ans -= mod;
      dp[now][a[0]][a[1]][a[2]][a[3]] = 0;
    } else
      for (int i = 1; i < h + 1; i++) {
        a[3] = i;
        ans += (dp[now][a[0]][a[1]][a[2]][a[3]] * pp) % mod;
        if (ans > mod) ans -= mod;
        dp[now][a[0]][a[1]][a[2]][a[3]] = 0;
      }
    return;
  }
  if (f)
    for (int i = 1; i < h + 1; i++) {
      a[n] = i;
      dfs2(n + 1, f, now);
    }
  else {
    a[n] = 0;
    dfs2(n + 1, 1, now);
    for (int i = 1; i < h + 1; i++) {
      a[n] = i;
      dfs2(n + 1, 0, now);
    }
  }
}
int main() {
  scanf("%d%d", &n, &h);
  dp[1][1][1][1][0] = 4;
  for (int i = 1; i < n; i++) {
    pp = pow(4, n - i, mod);
    for (int j = 1; j < h; j++)
      for (int k = 1; k < j + 1; k++)
        for (int t = 1; t < k + 1; t++) dp[(i + 1) & 1][j][k][t][0] = 0;
    for (int j = 1; j <= h; j++)
      for (int k = 1; k < j + 1; k++)
        for (int t = 0; t < k + 1; t++) dp[(i + 1) & 1][h][j][k][t] = 0;
    if (i < n - h + 1)
      for (int j = 1; j < h; j++)
        for (int k = 1; k < j + 1; k++)
          for (int t = 1; t < k + 1; t++) {
            for (int w = 0; w < 4; w++) {
              int a[4] = {j, k, t, 0};
              a[w] = 0;
              for (int w1 = w; w1 < 3; w1++) swap(a[w1], a[w1 + 1]);
              for (int w1 = 0; w1 < 3; w1++) a[w1] = a[w1] + 1;
              dp[(i + 1) & 1][a[0]][a[1]][a[2]][a[3]] += dp[i & 1][j][k][t][0];
              if (dp[(i + 1) & 1][a[0]][a[1]][a[2]][a[3]] > mod)
                dp[(i + 1) & 1][a[0]][a[1]][a[2]][a[3]] -= mod;
            }
          }
    else
      for (int j = 1; j <= h; j++)
        for (int k = 1; k < j + 1; k++)
          for (int t = 1; t < k + 1; t++) {
            ans += (dp[i & 1][j][k][t][0] * pp) % mod;
            dp[i & 1][j][k][t][0] = 0;
            if (ans > mod) ans -= mod;
          }
    for (int j = 1; j <= h; j++)
      for (int k = 1; k < j + 1; k++)
        for (int t = 0; t < k + 1; t++) {
          for (int w = 0; w < 4; w++) {
            int a[4] = {h, j, k, t};
            a[w] = a[w] == h ? h : 0;
            if (a[w] == 0) {
              for (int w1 = w; w1 < 3; w1++) swap(a[w1], a[w1 + 1]);
              for (int w1 = 0; w1 < 3; w1++)
                a[w1] = (a[w1] == h ? h : a[w1] + 1);
            } else
              for (int w1 = w + 1; w1 <= 3; w1++)
                a[w1] = (a[w1] == h ? h : a[w1] + 1);
            dp[(i + 1) & 1][a[0]][a[1]][a[2]][a[3]] += dp[i & 1][h][j][k][t];
            if (dp[(i + 1) & 1][a[0]][a[1]][a[2]][a[3]] > mod)
              dp[(i + 1) & 1][a[0]][a[1]][a[2]][a[3]] -= mod;
          }
        }
  }
  for (int j = 1; j <= h; j++)
    for (int k = 1; k < j + 1; k++)
      for (int t = 1; t < k + 1; t++) {
        ans += dp[n & 1][j][k][t][0];
        if (ans > mod) ans -= mod;
      }
  cout << ans << endl;
  return 0;
}
