#include <bits/stdc++.h>
const long double PI = acos(-1);
const long double eps = 0.0000000001;
const long long INF = 0x3fffffffffffffff;
const long long MOD = 1000000009;
long long dp[2][2][35][35][35], n, h;
bool now = true, lst = false;
void add(long long &A, const long long &B) { A = (A + B) % MOD; }
signed main() {
  std::ios::sync_with_stdio(false);
  std::cin >> n >> h;
  dp[now][1][h][h][h] = 1;
  for (long long i = 1; i <= n; ++i) {
    std::swap(now, lst);
    memset(dp[now], 0, sizeof(dp[now]));
    for (long long j = 0; j != 2; ++j)
      for (long long k = 0; k <= h; ++k)
        for (long long l = k; l <= h; ++l)
          for (long long p = l; p <= h; ++p) {
            add(dp[now][!!j][k ? k - 1 : 0][l ? l - 1 : 0][p ? p - 1 : 0],
                dp[lst][j][k][l][p]);
            if (j) {
              add(dp[now][!!k][l ? l - 1 : 0][p ? p - 1 : 0][h - 1],
                  dp[lst][j][k][l][p]);
              add(dp[now][!!l][k ? k - 1 : 0][p ? p - 1 : 0][h - 1],
                  dp[lst][j][k][l][p]);
              add(dp[now][!!p][k ? k - 1 : 0][l ? l - 1 : 0][h - 1],
                  dp[lst][j][k][l][p]);
            } else {
              add(dp[now][!!k][0][l ? l - 1 : 0][p ? p - 1 : 0],
                  dp[lst][j][k][l][p]);
              add(dp[now][!!l][0][k ? k - 1 : 0][p ? p - 1 : 0],
                  dp[lst][j][k][l][p]);
              add(dp[now][!!p][0][k ? k - 1 : 0][l ? l - 1 : 0],
                  dp[lst][j][k][l][p]);
            }
          }
  }
  long long ans = 0;
  for (long long i = 0; i != 2; ++i)
    for (long long j = 0; j <= h; ++j)
      for (long long k = 0; k <= h; ++k)
        for (long long l = 0; l <= h; ++l)
          if (i || j || k || l) add(ans, dp[now][i][j][k][l]);
  std::cout << ans << std::endl;
  return 0;
}
