#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000 * 1000 * 1000 + 9;
int N, H;
int f[2][2][33][33][33];
int trans(int x) { return x ? (x + 1) % H : 0; }
void upd(int h, int P, int I, int J, int K, int p, int i, int j, int k) {
  f[h][P][I][J][K] += f[h ^ 1][p][i][j][k];
  if (f[h][P][I][J][K] >= MOD) f[h][P][I][J][K] -= MOD;
}
int main() {
  cin >> N >> H;
  f[0][1][0][0][0] = 1;
  for (int h = 1; h <= N; h++) {
    memset(f[h & 1], 0, sizeof(f[h & 1]));
    for (int p = 0; p <= 1; p++) {
      for (int i = 0; i < H; i++)
        for (int j = 0; j < H; j++)
          for (int k = 0; k < H; k++) {
            int t = h & 1;
            int I = trans(i), J = trans(j), K = trans(k);
            upd(t, p, I, J, K, p, i, j, k);
            upd(t, h <= H || i, p, J, K, p, i, j, k);
            upd(t, h <= H || j, I, p, K, p, i, j, k);
            upd(t, h <= H || k, I, J, p, p, i, j, k);
          }
    }
  }
  int ans = 0;
  for (int i = 0; i <= H; i++)
    for (int j = 0; j <= H; j++)
      for (int k = 0; k <= H; k++) {
        ans += f[N & 1][1][i][j][k];
        if (ans >= MOD) ans -= MOD;
        if (i || j || k) ans += f[N & 1][0][i][j][k];
        if (ans >= MOD) ans -= MOD;
      }
  cout << ans << endl;
  return 0;
}
