#include <bits/stdc++.h>
using namespace std;
const long long P = 1000000009LL;
const int MAX_H = 32;
const int MAX = int(1e3) + 10;
int N, H;
long long dp[2][2][MAX_H][MAX_H][MAX_H];
void add(long long &x, long long y) {
  x += y;
  if (x >= P) x -= P;
}
int _(int h) { return h <= H ? h : H + 1; }
int main() {
  ios::sync_with_stdio(false);
  cin >> N >> H;
  dp[1][1][H + 1][H + 1][H + 1] = 4;
  for (int i = 1; i < N; i++)
    for (int liv = 0; liv < 2; liv++)
      for (int a = 1; a <= H + 1; a++)
        for (int b = 1; b <= H + 1; b++)
          for (int c = 1; c <= H + 1; c++) {
            add(dp[(i & 1) ^ 1][liv][_(a + 1)][_(b + 1)][_(c + 1)],
                dp[i & 1][liv][a][b][c]);
            add(dp[(i & 1) ^ 1][min(a, i) < H][liv ? 1 : H + 1][_(b + 1)]
                  [_(c + 1)],
                dp[i & 1][liv][a][b][c]);
            add(dp[(i & 1) ^ 1][min(b, i) < H][_(a + 1)][liv ? 1 : H + 1]
                  [_(c + 1)],
                dp[i & 1][liv][a][b][c]);
            add(dp[(i & 1) ^ 1][min(c, i) < H][_(a + 1)][_(b + 1)]
                  [liv ? 1 : H + 1],
                dp[i & 1][liv][a][b][c]);
            dp[i & 1][liv][a][b][c] = 0;
          }
  long long ans = 0;
  for (int a = 1; a <= H + 1; a++)
    for (int b = 1; b <= H + 1; b++)
      for (int c = 1; c <= H + 1; c++) {
        add(ans, dp[N & 1][1][a][b][c]);
        if (a < H || b < H || c < H) add(ans, dp[N & 1][0][a][b][c]);
      }
  cout << ans << endl;
  return 0;
}
