#include <bits/stdc++.h>
using namespace std;
const int H = 33;
const int MOD = 1e9 + 9;
int n, h, dp[2][2][H][H][H];
void inc(int &a, int b) {
  if (a += b, a >= MOD) a -= MOD;
}
void trans(int dp[2][H][H][H], int a, int b, int c, int d, int ii, int val) {
  int v[4] = {a, b, c, d};
  for (int i = 0; i < 4; ++i)
    if (i == ii)
      v[i] = !v[i] ? 0 : 1;
    else
      v[i] = (!v[i] || v[i] == h) ? 0 : ++v[i];
  sort(v, v + 4);
  inc(dp[v[0]][v[1]][v[2]][v[3]], val);
}
int main() {
  scanf("%d %d", &n, &h);
  dp[0][1][1][1][1] = 1;
  int now = 0, pre = 1;
  int ans = 0;
  for (int i = 1; i <= n + 1; ++i) {
    swap(now, pre);
    for (int a = 0; a <= 1; ++a)
      for (int b = a; b <= h; ++b)
        for (int c = b; c <= h; ++c)
          for (int d = c; d <= h; ++d) {
            int &val = dp[pre][a][b][c][d];
            if (i > n) {
              if (a + b + c + d) inc(ans, val);
              continue;
            }
            if (!val) continue;
            for (int i = 0; i < 4; ++i) trans(dp[now], a, b, c, d, i, val);
            val = 0;
          }
  }
  printf("%d\n", ans);
}
