#include <bits/stdc++.h>
int n, h;
int dynamics[1001][2][31][31][31];
int progress(int a) { return (a == 0 || a == h - 1) ? 0 : a + 1; }
inline void add(int& a, int b, int mod) { a = (a + b) % mod; }
int main(int argc, char* argv[]) {
  std::cin >> n >> h;
  if (h == 1)
    dynamics[1][1][0][0][0] = 4;
  else
    dynamics[1][1][1][1][1] = 4;
  for (int i = 1; i < n; i++) {
    for (int alive = 0; alive < 2; alive++) {
      for (int left = 0; left < h; left++) {
        for (int right = 0; right < h; right++) {
          for (int front = 0; front < h; front++) {
            int current = dynamics[i][alive][left][right][front];
            int next_left = progress(left);
            int next_right = progress(right);
            int next_front = progress(front);
            add(dynamics[i + 1][alive][next_left][next_right][next_front],
                current, 1e9 + 9);
            add(dynamics[i + 1][left > 0][alive][next_right][next_front],
                current, 1e9 + 9);
            add(dynamics[i + 1][right > 0][alive][next_left][next_front],
                current, 1e9 + 9);
            add(dynamics[i + 1][front > 0][alive][next_left][next_right],
                current, 1e9 + 9);
          }
        }
      }
    }
  }
  int result = 0;
  for (int alive = 0; alive < 2; alive++) {
    for (int left = 0; left < h; left++) {
      for (int right = 0; right < h; right++) {
        for (int front = 0; front < h; front++) {
          if (alive > 0 || left > 0 || right > 0 || front > 0) {
            add(result, dynamics[n][alive][left][right][front], 1e9 + 9);
          }
        }
      }
    }
  }
  std::cout << result << std::endl;
  return 0;
}
