#include <bits/stdc++.h>
using namespace std;
const int N = 30 + 3;
const int maxn = 1000 + 10;
const int mod = 1000000009;
int n, h, ans, f[maxn][N][N][N][2];
inline int min(int a, int b) { return a < b ? a : b; }
void Solve() {
  int a1, b1, c1, d, t;
  scanf("%d%d", &n, &h);
  f[0][0][0][0][1] = 1;
  for (int i = 0; i < n; ++i)
    for (int a = 0; a <= h; ++a)
      for (int b = 0; b <= h; ++b)
        for (int c = 0; c <= h; ++c)
          for (int j = 0; j <= 1; ++j) {
            t = f[i][a][b][c][j];
            if (!t) continue;
            a1 = min(a + 1, h);
            b1 = min(b + 1, h);
            c1 = min(c + 1, h);
            d = j ? 1 : h;
            t %= mod;
            (f[i + 1][a1][b1][c1][j] += t) %= mod;
            (f[i + 1][d][b1][c1][a < h] += t) %= mod;
            (f[i + 1][a1][d][c1][b < h] += t) %= mod;
            (f[i + 1][a1][b1][d][c < h] += t) %= mod;
          }
  int ans = 0;
  for (int a = 0; a <= h; ++a)
    for (int b = 0; b <= h; ++b)
      for (int c = 0; c <= h; ++c)
        for (int j = 0; j <= 1; ++j)
          if (a < h || b < h || c < h || j) (ans += f[n][a][b][c][j]) %= mod;
  printf("%d\n", ans);
}
int main() {
  Solve();
  fclose(stdin);
  fclose(stdout);
  return 0;
}
