#include <bits/stdc++.h>
using namespace std;
const long long N = 1005, H = 35, MOD = 1e9 + 9;
long long dp[2][2][H][H][H], n, h;
void add(long long &a, long long b) { a = (a + b) % MOD; }
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> h;
  dp[1][1][1][1][1] = 4;
  for (long long id = 1; id <= n - 1; ++id) {
    long long i = id & 1;
    memset(dp[i ^ 1], 0, sizeof dp[i ^ 1]);
    for (long long a = 0; a < 2; ++a)
      for (long long b = 0; b < h + 1; ++b)
        for (long long c = 0; c < h + 1; ++c)
          for (long long d = 0; d < h + 1; ++d) {
            long long cur = dp[i][a][b][c][d];
            if (cur == 0) continue;
            add(dp[i ^ 1][a][min(b + 1, h)][min(c + 1, h)][min(d + 1, h)], cur);
            add(dp[i ^ 1][b < h][min(c + 1, h)][min(d + 1, h)][a == 1 ? 1 : h],
                cur);
            add(dp[i ^ 1][c < h][min(d + 1, h)][a == 1 ? 1 : h][min(b + 1, h)],
                cur);
            add(dp[i ^ 1][d < h][a == 1 ? 1 : h][min(b + 1, h)][min(c + 1, h)],
                cur);
          }
  }
  long long res = 0;
  for (long long a = 0; a < 2; ++a)
    for (long long b = 0; b < h + 1; ++b)
      for (long long c = 0; c < h + 1; ++c)
        for (long long 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 << endl;
  return 0;
}
