#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000009;
const int MAX_H = 32;
int dp[2][2][MAX_H][MAX_H][MAX_H];
int n, h;
void add(int &a, int b) { (a += b) %= MOD; }
int main() {
  cin >> n >> h;
  dp[0][1][0][0][0] = 1;
  for (int i = 0; i < n; i++) {
    int cur = i & 1;
    int nxt = !cur;
    for (int a = 0; a <= 1; a++) {
      for (int b = 0; b <= h + 1; b++) {
        for (int c = 0; c <= h + 1; c++) {
          for (int d = 0; d <= h + 1; d++) {
            dp[nxt][a][b][c][d] = 0;
          }
        }
      }
    }
    for (int a = 0; a <= 1; a++) {
      for (int b = 0; b <= h + 1; b++) {
        for (int c = 0; c <= h + 1; c++) {
          for (int d = 0; d <= h + 1; d++) {
            if (dp[cur][a][b][c][d] == 0) {
              continue;
            }
            int val = dp[cur][a][b][c][d];
            add(dp[nxt][a][min(h + 1, b + 1)][min(h + 1, c + 1)]
                  [min(h + 1, d + 1)],
                val);
            add(dp[nxt][b + 1 <= h][min(h + 1, c + 1)][min(h + 1, d + 1)]
                  [a == 1 ? 1 : h + 1],
                val);
            add(dp[nxt][c + 1 <= h][min(h + 1, d + 1)][a == 1 ? 1 : h + 1]
                  [min(h + 1, b + 1)],
                val);
            add(dp[nxt][d + 1 <= h][a == 1 ? 1 : h + 1][min(h + 1, b + 1)]
                  [min(h + 1, c + 1)],
                val);
          }
        }
      }
    }
  }
  int res = 0;
  for (int a = 0; a <= 1; a++) {
    for (int b = 0; b <= h + 1; b++) {
      for (int c = 0; c <= h + 1; c++) {
        for (int d = 0; d <= h + 1; d++) {
          if (a == 1 || b < h || c < h || d < h) {
            add(res, dp[n & 1][a][b][c][d]);
          }
        }
      }
    }
  }
  cout << res;
  return 0;
}
