#include <bits/stdc++.h>
using namespace std;
int n, h;
int func(int a) {
  if (a == 0 || a == (h - 1)) return 0;
  return a + 1;
}
int dp[1001][31][31][31][2];
int main() {
  cin >> n >> h;
  dp[1][0][0][0][1] = 4;
  for (int i = 1; i < n; i++) {
    for (int j = 0; j < h; j++) {
      for (int k = 0; k < h; k++) {
        for (int l = 0; l < h; l++) {
          for (int m = 0; m < 2; m++) {
            int cur = dp[i][j][k][l][m];
            dp[i + 1][func(j)][func(k)][func(l)][m] =
                (dp[i + 1][func(j)][func(k)][func(l)][m] + cur) % 1000000009;
            dp[i + 1][m][func(k)][func(l)][(j > 0 || i < h)] =
                (dp[i + 1][m][func(k)][func(l)][(j > 0 || i < h)] + cur) %
                1000000009;
            dp[i + 1][func(j)][m][func(l)][(k > 0 || i < h)] =
                (dp[i + 1][func(j)][m][func(l)][(k > 0 || i < h)] + cur) %
                1000000009;
            dp[1 + i][func(j)][func(k)][m][(l > 0 || i < h)] =
                (dp[1 + i][func(j)][func(k)][m][(l > 0 || i < h)] + cur) %
                1000000009;
          }
        }
      }
    }
  }
  int ans = 0;
  for (int j = 0; j < h; j++) {
    for (int k = 0; k < h; k++) {
      for (int l = 0; l < h; l++) {
        ans = (ans + dp[n][j][k][l][1]) % 1000000009;
        if ((l + j + k) > 0) ans = (ans + dp[n][j][k][l][0]) % 1000000009;
      }
    }
  }
  cout << ans << endl;
}
