#include <bits/stdc++.h>
using namespace std;
template <typename typ>
void vout(vector<typ>& v) {
  for (int vint = 0; vint < (int)(v).size(); vint++) cout << (v)[vint] << ' ';
  cout << endl;
}
template <typename typ>
void arrout(typ* arr, int l) {
  for (int i = 0; i < l; i++) cout << arr[i] << ' ';
  cout << endl;
}
int mod = 1000000009;
int main() {
  int n, h;
  cin >> n >> h;
  int dp[2][2][h + 1][h + 1][h + 1];
  memset(dp, 0, sizeof(dp));
  dp[0][1][1][1][1] = 4;
  for (int i = 0; i < n - 1; ++i)
    for (int alive = 0; alive < 2; ++alive)
      for (int a = 1; a <= h; ++a)
        for (int b = 1; b <= h; ++b)
          for (int c = 1; c <= h; ++c) {
            int& cur = dp[i & 1][alive][a][b][c];
            dp[i & 1 ^ 1][alive][min(a + 1, h)][min(b + 1, h)][min(c + 1, h)] =
                (dp[i & 1 ^ 1][alive][min(a + 1, h)][min(b + 1, h)]
                   [min(c + 1, h)] +
                 +cur) %
                mod;
            dp[i & 1 ^ 1][a != h][alive ? 1 : h][min(b + 1, h)][min(c + 1, h)] =
                (dp[i & 1 ^ 1][a != h][alive ? 1 : h][min(b + 1, h)]
                   [min(c + 1, h)] +
                 cur) %
                mod;
            dp[i & 1 ^ 1][b != h][min(a + 1, h)][alive ? 1 : h][min(c + 1, h)] =
                (dp[i & 1 ^ 1][b != h][min(a + 1, h)][alive ? 1 : h]
                   [min(c + 1, h)] +
                 cur) %
                mod;
            dp[i & 1 ^ 1][c != h][min(a + 1, h)][min(b + 1, h)][alive ? 1 : h] =
                (dp[i & 1 ^ 1][c != h][min(a + 1, h)][min(b + 1, h)]
                   [alive ? 1 : h] +
                 cur) %
                mod;
            cur = 0;
          }
  long long ans = 0;
  for (int a = 1; a <= h; ++a)
    for (int b = 1; b <= h; ++b)
      for (int c = 1; c <= h; ++c)
        for (int alive = 0; alive < 2; ++alive)
          if (a < h || b < h || c < h || alive)
            ans = (ans + dp[(n - 1) & 1][alive][a][b][c]) % mod;
  cout << (ans) << endl;
}
