#include <bits/stdc++.h>
using namespace std;
int n, h, f[2][2][31][31][31];
int main(void) {
  cin >> n >> h;
  memset(f, 0, sizeof f);
  f[0][1][0][0][0] = 1;
  for (int i = int(0), ni = int(n); i <= ni; i++) {
    memset(f[1 - (i & 1)], 0, sizeof f[1 - (i & 1)]);
    for (int a = int(0), na = int(h); a <= na; a++)
      for (int b = int(0), nb = int(h); b <= nb; b++)
        for (int c = int(0), nc = int(h); c <= nc; c++)
          for (int k = int(0), nk = int(1); k <= nk; k++) {
            int z = i & 1, v = f[z][k][a][b][c], d = k ? 1 : h;
            if (v == 0) continue;
            (f[1 - z][a < h][min(b + 1, h)][min(c + 1, h)][d] += v) %=
                1000000009;
            (f[1 - z][b < h][min(a + 1, h)][min(c + 1, h)][d] += v) %=
                1000000009;
            (f[1 - z][c < h][min(a + 1, h)][min(b + 1, h)][d] += v) %=
                1000000009;
            (f[1 - z][k][min(a + 1, h)][min(b + 1, h)][min(c + 1, h)] += v) %=
                1000000009;
          }
  }
  int ans = 0;
  for (int a = int(0), na = int(h); a <= na; a++)
    for (int b = int(0), nb = int(h); b <= nb; b++)
      for (int c = int(0), nc = int(h); c <= nc; c++)
        for (int k = int(0), nk = int(1); k <= nk; k++)
          if (a < h || b < h || c < h || k)
            (ans += f[n & 1][k][a][b][c]) %= 1000000009;
  cout << ans << endl;
  return 0;
}
