#include <bits/stdc++.h>
using namespace std;
const int tam = 100010;
const int MOD = 1000000009;
const int MOD1 = 998244353;
const double EPS = 1e-9;
const double PI = acos(-1);
long long dp[2][33][33][33][33];
long long per[33][33][33];
long long par[33][33][33];
int main() {
  int n, h;
  cin >> n >> h;
  for (int i = 1; i < 33; i++) {
    for (int j = i; j < 33; j++) {
      for (int k = j; k < 33; k++) {
        map<int, int> ma;
        ma[i]++;
        ma[j]++;
        ma[k]++;
        per[i][j][k] = 6;
        for (auto pa : ma) {
          int divi = 1, con = 1;
          while (pa.second--) {
            divi *= con;
            con++;
          }
          per[i][j][k] /= divi;
        }
        ma[h + 1]++;
        par[i][j][k] = 24;
        for (auto pa : ma) {
          int divi = 1, con = 1;
          while (pa.second--) {
            divi *= con;
            con++;
          }
          par[i][j][k] /= divi;
        }
      }
    }
  }
  int now, last, hcon, dis, i, j, k, l, ip, jp, kp, lp, ucon, perm;
  dp[0][1][1][1][1] = 1;
  vector<int> ava(4);
  set<pair<pair<int, int>, pair<int, int>>> st;
  vector<pair<pair<int, int>, pair<int, int>>> cas, casp;
  for (int i = 1; i < h + 2; i++) {
    ip = min(h + 1, i + 1);
    for (int j = 1; j < h + 2; j++) {
      jp = min(h + 1, j + 1);
      for (int k = 1; k < h + 2; k++) {
        kp = min(h + 1, k + 1);
        hcon = (i == h + 1) + (j == h + 1) + (k == h + 1);
        ucon = (i == 1) + (j == 1) + (k == 1);
        for (int l = 1; l < h + 2; l++) {
          if (hcon == 3 && l == h + 1) break;
          lp = min(h + 1, l + 1);
          vector<int> casu;
          casu.push_back(i);
          casu.push_back(j);
          casu.push_back(k);
          casu.push_back(l);
          sort((casu).begin(), (casu).end());
          st.insert(make_pair(make_pair(casu[0], casu[1]),
                              make_pair(casu[2], casu[3])));
          if (ucon == 0 && hcon == 0 && l == 1) l = h;
        }
      }
    }
  }
  for (auto a : st) {
    cas.push_back(a);
    casp.push_back(make_pair(make_pair(min(h + 1, a.first.first + 1),
                                       min(h + 1, a.first.second + 1)),
                             make_pair(min(h + 1, a.second.first + 1),
                                       min(h + 1, a.second.second + 1))));
  }
  for (int x = 1; x < n + 1; x++) {
    now = x % 2;
    last = abs(now - 1);
    for (int i = 0; i < cas.size(); i++)
      dp[now][cas[i].first.first][cas[i].first.second][cas[i].second.first]
        [cas[i].second.second] = 0;
    for (int z = 0; z < cas.size(); z++) {
      i = cas[z].first.first, j = cas[z].first.second, k = cas[z].second.first,
      l = cas[z].second.second;
      ip = casp[z].first.first, jp = casp[z].first.second,
      kp = casp[z].second.first, lp = casp[z].second.second;
      if (i != h + 1)
        dp[now][1][jp][kp][lp] += dp[last][i][j][k][l];
      else
        dp[now][ip][jp][kp][lp] += dp[last][i][j][k][l];
      if (j != h + 1)
        dp[now][1][ip][kp][lp] += dp[last][i][j][k][l];
      else
        dp[now][ip][jp][kp][lp] += dp[last][i][j][k][l];
      if (k != h + 1)
        dp[now][1][ip][jp][lp] += dp[last][i][j][k][l];
      else
        dp[now][ip][jp][kp][lp] += dp[last][i][j][k][l];
      if (l != h + 1)
        dp[now][1][ip][jp][kp] += dp[last][i][j][k][l];
      else
        dp[now][ip][jp][kp][lp] += dp[last][i][j][k][l];
    }
    for (int i = 0; i < cas.size(); i++)
      dp[now][cas[i].first.first][cas[i].first.second][cas[i].second.first]
        [cas[i].second.second] %= MOD;
  }
  long long res = 0;
  for (int i = 0; i < cas.size(); i++)
    res = (res + dp[now][cas[i].first.first][cas[i].first.second]
                   [cas[i].second.first][cas[i].second.second]) %
          MOD;
  cout << res << '\n';
  return 0;
}
