#include <bits/stdc++.h>
using namespace std;
int n, h, dp[1005][32][32][32][2], ans = 0;
void f(int& x, int y) {
  x += y;
  if (x > 1000000009) x -= 1000000009;
}
int main() {
  memset(dp, 0, sizeof dp);
  cin >> n >> h;
  dp[0][2][2][2][1] = 4;
  for (int i = 1; i < n; i++) {
    for (int x = 2; x <= h + 1; x++) {
      for (int y = x; y <= h + 1; y++) {
        for (int z = y; z <= h + 1; z++) {
          for (int o = 0; o <= 1; o++) {
            int old = dp[i - 1][x][y][z][o];
            if (!old) continue;
            int u = x > h ? x : x + 1, v = y > h ? y : y + 1,
                w = z > h ? z : z + 1;
            f(dp[i][u][v][w][o], old);
            if (o) {
              f(dp[i][2][v][w][x <= h], old);
              f(dp[i][2][u][w][y <= h], old);
              f(dp[i][2][u][v][z <= h], old);
            } else {
              f(dp[i][v][w][h + 1][x <= h], old);
              f(dp[i][u][w][h + 1][y <= h], old);
              f(dp[i][u][v][h + 1][z <= h], old);
            }
          }
        }
      }
    }
  }
  for (int x = 0; x <= h + 1; x++) {
    for (int y = 0; y <= h + 1; y++) {
      for (int z = 0; z <= h + 1; z++) {
        for (int o = 0; o <= 1; o++) {
          if (x <= h || y <= h || z <= h || o) {
            f(ans, dp[n - 1][x][y][z][o]);
          }
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}
