#include <bits/stdc++.h>
using namespace std;
const int mo = 1e9 + 9;
int n, h, dp[1005][2][32][32][32];
void upd(int &x, const int &y) { (x += y) >= mo ? x -= mo : 0; }
int main() {
  scanf("%d%d", &n, &h);
  dp[0][1][0][0][0] = 1;
  for (int v, i = 1; i <= n; i++) {
    for (int a = 0; a < 2; a++) {
      for (int b = 0; b <= h; b++) {
        for (int c = 0; c <= h; c++) {
          for (int d = 0; d <= h; d++)
            if (v = dp[i - 1][a][b][c][d]) {
              upd(dp[i][a][b == h ? h : b + 1][c == h ? h : c + 1]
                    [d == h ? h : d + 1],
                  v);
              upd(dp[i][b == h ? 0 : 1][c == h ? h : c + 1][d == h ? h : d + 1]
                    [a ? 1 : h],
                  v);
              upd(dp[i][c == h ? 0 : 1][d == h ? h : d + 1][a ? 1 : h]
                    [b == h ? h : b + 1],
                  v);
              upd(dp[i][d == h ? 0 : 1][a ? 1 : h][b == h ? h : b + 1]
                    [c == h ? h : c + 1],
                  v);
            }
        }
      }
    }
  }
  int ans = 0;
  for (int a = 0; a < 2; a++) {
    for (int b = 0; b <= h; b++) {
      for (int c = 0; c <= h; c++) {
        for (int d = 0; d <= h; d++)
          if (a || b < h || c < h || d < h) {
            upd(ans, dp[n][a][b][c][d]);
          }
      }
    }
  }
  printf("%d\n", ans);
  return 0;
}
