#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000009;
inline int add(int a, int b) {
  if ((a += b) >= mod) a -= mod;
  return a;
}
inline void upd(int &a, int b) { a = add(a, b); }
int n, h, dp[2][31][31][31][31];
int main() {
  scanf("%d%d", &n, &h);
  int cur = 0;
  dp[0][0][0][0][0] = 1;
  for (int i = 0; i < n; i++) {
    cur ^= 1;
    memset(dp[cur], 0, sizeof(dp[cur]));
    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++) {
            int val = dp[cur ^ 1][a][b][c][d];
            if (val) {
              upd(dp[cur][a][min(b + 1, h)][min(c + 1, h)][min(d + 1, h)], val);
              upd(dp[cur][b + 1 > h][min(c + 1, h)][min(d + 1, h)][a ? h : 1],
                  val);
              upd(dp[cur][c + 1 > h][min(d + 1, h)][a ? h : 1][min(b + 1, h)],
                  val);
              upd(dp[cur][d + 1 > h][a ? h : 1][min(b + 1, h)][min(c + 1, h)],
                  val);
            }
          }
        }
      }
    }
  }
  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)
            ans = add(ans, dp[cur][a][b][c][d]);
        }
      }
    }
  }
  printf("%d\n", ans);
  return 0;
}
