#include <bits/stdc++.h>
using namespace std;
int dp[2][35][35][35][35][2];
int mod = 1000000009;
vector<int> a[32][32][32][32];
int main() {
  int n, h;
  cin >> n >> h;
  for (int i = (0); i < (h + 2); ++i)
    for (int j = (0); j < (h + 2); ++j)
      for (int k = (0); k < (h + 2); ++k)
        for (int c = (0); c < (h + 2); ++c) {
          a[i][j][k][c].push_back(i);
          a[i][j][k][c].push_back(j);
          a[i][j][k][c].push_back(k);
          a[i][j][k][c].push_back(c);
          sort(a[i][j][k][c].begin(), a[i][j][k][c].end());
        }
  dp[0][1][1][1][1][0] = 1;
  int v = 0;
  for (int p = (1); p < (n + 1); ++p) {
    int nv = v ^ 1;
    for (int h1 = (0); h1 < (h + 2); ++h1)
      for (int h2 = (h1); h2 < (h + 2); ++h2)
        for (int h3 = (h2); h3 < (h + 2); ++h3)
          for (int h4 = (h3); h4 < (h + 2); ++h4)
            for (int f = (0); f < (2); ++f) {
              if (dp[v][h1][h2][h3][h4][f] == 0) continue;
              int nh1, nh2, nh3, nh4, nnh1, nnh2, nnh3, nnh4;
              int nf = f;
              if (h1 != h + 1)
                nh1 = 1;
              else
                nh1 = h + 1;
              nh2 = ((h + 1 < h2 + 1) ? (h + 1) : (h2 + 1));
              nh3 = ((h + 1 < h3 + 1) ? (h + 1) : (h3 + 1));
              nh4 = ((h + 1 < h4 + 1) ? (h + 1) : (h4 + 1));
              if ((h1 != h + 1) && (p >= n - h + 1)) nf = 1;
              nnh1 = a[nh1][nh2][nh3][nh4][0];
              nnh2 = a[nh1][nh2][nh3][nh4][1];
              nnh3 = a[nh1][nh2][nh3][nh4][2];
              nnh4 = a[nh1][nh2][nh3][nh4][3];
              dp[nv][nnh1][nnh2][nnh3][nnh4][nf] += dp[v][h1][h2][h3][h4][f];
              if (dp[nv][nnh1][nnh2][nnh3][nnh4][nf] >= mod)
                dp[nv][nnh1][nnh2][nnh3][nnh4][nf] -= mod;
              nf = f;
              if (h2 != h + 1)
                nh2 = 1;
              else
                nh2 = h + 1;
              nh1 = ((h + 1 < h1 + 1) ? (h + 1) : (h1 + 1));
              nh3 = ((h + 1 < h3 + 1) ? (h + 1) : (h3 + 1));
              nh4 = ((h + 1 < h4 + 1) ? (h + 1) : (h4 + 1));
              if ((h2 != h + 1) && (p >= n - h + 1)) nf = 1;
              nnh1 = a[nh1][nh2][nh3][nh4][0];
              nnh2 = a[nh1][nh2][nh3][nh4][1];
              nnh3 = a[nh1][nh2][nh3][nh4][2];
              nnh4 = a[nh1][nh2][nh3][nh4][3];
              dp[nv][nnh1][nnh2][nnh3][nnh4][nf] += dp[v][h1][h2][h3][h4][f];
              if (dp[nv][nnh1][nnh2][nnh3][nnh4][nf] >= mod)
                dp[nv][nnh1][nnh2][nnh3][nnh4][nf] -= mod;
              nf = f;
              if (h3 != h + 1)
                nh3 = 1;
              else
                nh3 = h + 1;
              nh1 = ((h + 1 < h1 + 1) ? (h + 1) : (h1 + 1));
              nh2 = ((h + 1 < h2 + 1) ? (h + 1) : (h2 + 1));
              nh4 = ((h + 1 < h4 + 1) ? (h + 1) : (h4 + 1));
              if ((h3 != h + 1) && (p >= n - h + 1)) nf = 1;
              nnh1 = a[nh1][nh2][nh3][nh4][0];
              nnh2 = a[nh1][nh2][nh3][nh4][1];
              nnh3 = a[nh1][nh2][nh3][nh4][2];
              nnh4 = a[nh1][nh2][nh3][nh4][3];
              dp[nv][nnh1][nnh2][nnh3][nnh4][nf] += dp[v][h1][h2][h3][h4][f];
              if (dp[nv][nnh1][nnh2][nnh3][nnh4][nf] >= mod)
                dp[nv][nnh1][nnh2][nnh3][nnh4][nf] -= mod;
              nf = f;
              if (h4 != h + 1)
                nh4 = 1;
              else
                nh4 = h + 1;
              nh1 = ((h + 1 < h1 + 1) ? (h + 1) : (h1 + 1));
              nh2 = ((h + 1 < h2 + 1) ? (h + 1) : (h2 + 1));
              nh3 = ((h + 1 < h3 + 1) ? (h + 1) : (h3 + 1));
              if ((h4 != h + 1) && (p >= n - h + 1)) nf = 1;
              nnh1 = a[nh1][nh2][nh3][nh4][0];
              nnh2 = a[nh1][nh2][nh3][nh4][1];
              nnh3 = a[nh1][nh2][nh3][nh4][2];
              nnh4 = a[nh1][nh2][nh3][nh4][3];
              dp[nv][nnh1][nnh2][nnh3][nnh4][nf] += dp[v][h1][h2][h3][h4][f];
              if (dp[nv][nnh1][nnh2][nnh3][nnh4][nf] >= mod)
                dp[nv][nnh1][nnh2][nnh3][nnh4][nf] -= mod;
            }
    for (int h1 = (0); h1 < (h + 2); ++h1)
      for (int h2 = (h1); h2 < (h + 2); ++h2)
        for (int h3 = (h2); h3 < (h + 2); ++h3)
          for (int h4 = (h3); h4 < (h + 2); ++h4)
            for (int f = (0); f < (2); ++f) dp[v][h1][h2][h3][h4][f] = 0;
    v ^= 1;
  }
  int res = 0;
  for (int h1 = (0); h1 < (h + 2); ++h1)
    for (int h2 = (h1); h2 < (h + 2); ++h2)
      for (int h3 = (h2); h3 < (h + 2); ++h3)
        for (int h4 = (h3); h4 < (h + 2); ++h4) {
          res += dp[v][h1][h2][h3][h4][1];
          if (res >= mod) res -= mod;
        }
  cout << res << endl;
  return 0;
}
