#include <bits/stdc++.h>
using namespace std;
int n, m;
long long dp[2][35 * 35 * 35 * 35];
int Dp() {
  static int sta[2][300000], use[35 * 35 * 35 * 35];
  long long *f = dp[0], *g = dp[1];
  int s[4], N[2] = {0}, cur = 0, id = 0;
  f[0] = 1, sta[0][++N[0]] = 0;
  for (int i = 0; i < n; ++i) {
    ++id;
    N[cur ^ 1] = 0;
    for (int j = 1; j <= N[cur]; ++j) {
      int S = sta[cur][j], a = S >> 15, b = S >> 10 & 31, c = S >> 5 & 31,
          d = S & 31;
      if (use[S] == id) continue;
      use[S] = id;
      int val = f[S] % 1000000009, newS;
      s[0] = a < m ? 0 : m + 1, s[1] = min(m + 1, b + 1),
      s[2] = min(m + 1, c + 1), s[3] = min(m + 1, d + 1), sort(s, s + 4);
      newS = ((s[0] << 5 | s[1]) << 5 | s[2]) << 5 | s[3], g[newS] += val,
      sta[cur ^ 1][++N[cur ^ 1]] = newS;
      s[0] = b < m ? 0 : m + 1, s[1] = min(m + 1, a + 1),
      s[2] = min(m + 1, c + 1), s[3] = min(m + 1, d + 1), sort(s, s + 4);
      newS = ((s[0] << 5 | s[1]) << 5 | s[2]) << 5 | s[3], g[newS] += val,
      sta[cur ^ 1][++N[cur ^ 1]] = newS;
      s[0] = c < m ? 0 : m + 1, s[1] = min(m + 1, a + 1),
      s[2] = min(m + 1, b + 1), s[3] = min(m + 1, d + 1), sort(s, s + 4);
      newS = ((s[0] << 5 | s[1]) << 5 | s[2]) << 5 | s[3], g[newS] += val,
      sta[cur ^ 1][++N[cur ^ 1]] = newS;
      s[0] = d < m ? 0 : m + 1, s[1] = min(m + 1, a + 1),
      s[2] = min(m + 1, b + 1), s[3] = min(m + 1, c + 1), sort(s, s + 4);
      newS = ((s[0] << 5 | s[1]) << 5 | s[2]) << 5 | s[3], g[newS] += val,
      sta[cur ^ 1][++N[cur ^ 1]] = newS;
      f[S] = 0;
    }
    cur ^= 1, swap(f, g);
  }
  int ans = 0;
  ++id;
  for (int i = 1; i <= N[cur]; ++i)
    if ((sta[cur][i] >> 15) <= m - 1 && use[sta[cur][i]] != id) {
      ans = (ans + f[sta[cur][i]]) % 1000000009;
      use[sta[cur][i]] = id;
    }
  return ans;
}
int main() {
  cin >> n >> m;
  cout << Dp() << endl;
  return 0;
}
