#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000009;
int n, h;
long long dp[2][2][32][32][32];
inline int inc(int x) { return min(h, x + 1); }
int main(void) {
  int temp, index, j4;
  cin >> n >> h;
  dp[0][1][0][0][0] = 1;
  for (int i = 0; i < n; ++i) {
    for (int k = 0; k < 2; ++k) {
      for (int j1 = 0; j1 <= h; ++j1) {
        for (int j2 = 0; j2 <= h; ++j2) {
          for (int j3 = 0; j3 <= h; ++j3) {
            temp = dp[i & 1][k][j1][j2][j3];
            if (!temp) continue;
            dp[i & 1][k][j1][j2][j3] = 0;
            index = i & 1 ^ 1;
            if (k == 1)
              j4 = 1;
            else
              j4 = h;
            dp[index][k][inc(j1)][inc(j2)][inc(j3)] += temp;
            dp[index][k][inc(j1)][inc(j2)][inc(j3)] %= mod;
            dp[index][j1 < h][j4][inc(j2)][inc(j3)] += temp;
            dp[index][j1 < h][j4][inc(j2)][inc(j3)] %= mod;
            dp[index][j2 < h][j4][inc(j1)][inc(j3)] += temp;
            dp[index][j2 < h][j4][inc(j1)][inc(j3)] %= mod;
            dp[index][j3 < h][j4][inc(j1)][inc(j2)] += temp;
            dp[index][j3 < h][j4][inc(j1)][inc(j2)] %= mod;
          }
        }
      }
    }
  }
  long long ans = 0;
  for (int k = 0; k < 2; ++k) {
    for (int j1 = 0; j1 <= h; ++j1) {
      for (int j2 = 0; j2 <= h; ++j2) {
        for (int j3 = 0; j3 <= h; ++j3) {
          if (k == 1 || j1 < h || j2 < h || j3 < h)
            ans = (ans + dp[n & 1][k][j1][j2][j3]) % mod;
        }
      }
    }
  }
  cout << ans << endl;
}
