#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 9;
const int maxh = 35;
int n, h, m, ans;
int dp[2][238576];
int state[238577][4];
int match[maxh][maxh][maxh][maxh];
inline void add(int &x, int y) { (x += y) -= (x >= INF ? INF : 0); }
int main() {
  scanf("%d%d", &n, &h);
  dp[0][0] = 1;
  int p = 0, q = 1;
  for (int i = (0); i <= (h + 1); ++i)
    for (int j = (0); j <= (h + 1); ++j)
      for (int k = (0); k <= (h + 1); ++k)
        for (int l = (0); l <= (h + 1); ++l) match[i][j][k][l] = 238575;
  for (int i = (0); i <= (h + 1); ++i)
    for (int j = (0); j <= (h + 1); ++j)
      for (int k = (0); k <= (h + 1); ++k)
        for (int l = (0); l <= (h + 1); ++l) {
          if ((!(i % (h + 1)) || !(j % (h + 1)) || !(k % (h + 1)) ||
               !(l % (h + 1))) &&
              (i <= j && j <= k && k <= l)) {
            state[m][0] = i, state[m][1] = j, state[m][2] = k, state[m][3] = l;
            match[i][j][k][l] = match[i][j][l][k] = match[i][l][j][k] =
                match[i][l][k][j] = match[i][k][j][l] = match[i][k][l][j] = m;
            match[j][i][k][l] = match[j][i][l][k] = match[j][k][i][l] =
                match[j][k][l][i] = match[j][l][k][i] = match[j][l][i][l] = m;
            match[k][i][j][l] = match[k][i][l][j] = match[k][j][i][l] =
                match[k][j][l][i] = match[k][l][i][j] = match[k][l][j][i] = m;
            match[l][i][j][k] = match[l][i][k][j] = match[l][j][i][k] =
                match[l][j][k][i] = match[l][k][i][j] = match[l][k][j][i] = m++;
          }
        }
  for (int it = (0); it < (n); ++it) {
    for (int s = (0); s < (m); ++s)
      if (dp[p][s]) {
        int a = min(state[s][0] + 1, h + 1), b = min(state[s][1] + 1, h + 1),
            c = min(state[s][2] + 1, h + 1), d = min(state[s][3] + 1, h + 1);
        int res = dp[p][s];
        add(dp[q][match[a == h + 1 ? h + 1 : 0][b][c][d]], res);
        add(dp[q][match[a][b == h + 1 ? h + 1 : 0][c][d]], res);
        add(dp[q][match[a][b][c == h + 1 ? h + 1 : 0][d]], res);
        add(dp[q][match[a][b][c][d == h + 1 ? h + 1 : 0]], res);
      }
    p ^= 1, q ^= 1;
    memset(dp[q], 0, sizeof(dp[q]));
  }
  for (int i = (0); i < (m); ++i)
    if (state[i][0] < h || state[i][1] < h || state[i][2] < h ||
        state[i][3] < h)
      add(ans, dp[n & 1][i]);
  printf("%d\n", ans);
  return 0;
}
