#include <bits/stdc++.h>
using namespace std;
template <class T>
bool checkMin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool checkMax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
const int INF = 1e9;
const int mod = 1000000009;
const int M = 30 + 5;
int n, h;
int dp[2][2][M][M][M];
int main() {
  while (scanf("%d %d", &n, &h) != EOF) {
    memset(dp, 0, sizeof(dp));
    dp[1][1][0][0][0] = 4;
    for (int i = (1); i <= (n - 1); i++) {
      memset(dp[!(i & 1)], 0, sizeof(dp[!(i & 1)]));
      for (int alive = 0; alive < (2); alive++)
        for (int a = 0; a < (h); a++)
          for (int b = 0; b < (h); b++)
            for (int c = 0; c < (h); c++) {
              int& r = dp[i & 1][alive][a][b][c];
              {
                dp[!(i & 1)][alive][(((a) + ((a) > 0)) % (h))]
                  [(((b) + ((b) > 0)) % (h))][(((c) + ((c) > 0)) % (h))] += r;
                if (dp[!(i & 1)][alive][(((a) + ((a) > 0)) % (h))]
                      [(((b) + ((b) > 0)) % (h))][(((c) + ((c) > 0)) % (h))] >=
                    mod)
                  dp[!(i & 1)][alive][(((a) + ((a) > 0)) % (h))]
                    [(((b) + ((b) > 0)) % (h))][(((c) + ((c) > 0)) % (h))] -=
                      mod;
              };
              {
                dp[!(i & 1)][(i < h || a > 0)][alive][(((b) + ((b) > 0)) % (h))]
                  [(((c) + ((c) > 0)) % (h))] += r;
                if (dp[!(i & 1)][(i < h || a > 0)][alive]
                      [(((b) + ((b) > 0)) % (h))][(((c) + ((c) > 0)) % (h))] >=
                    mod)
                  dp[!(i & 1)][(i < h || a > 0)][alive]
                    [(((b) + ((b) > 0)) % (h))][(((c) + ((c) > 0)) % (h))] -=
                      mod;
              };
              {
                dp[!(i & 1)][(i < h || b > 0)][(((a) + ((a) > 0)) % (h))][alive]
                  [(((c) + ((c) > 0)) % (h))] += r;
                if (dp[!(i & 1)][(i < h || b > 0)][(((a) + ((a) > 0)) % (h))]
                      [alive][(((c) + ((c) > 0)) % (h))] >= mod)
                  dp[!(i & 1)][(i < h || b > 0)][(((a) + ((a) > 0)) % (h))]
                    [alive][(((c) + ((c) > 0)) % (h))] -= mod;
              };
              {
                dp[!(i & 1)][(i < h || c > 0)][(((a) + ((a) > 0)) % (h))]
                  [(((b) + ((b) > 0)) % (h))][alive] += r;
                if (dp[!(i & 1)][(i < h || c > 0)][(((a) + ((a) > 0)) % (h))]
                      [(((b) + ((b) > 0)) % (h))][alive] >= mod)
                  dp[!(i & 1)][(i < h || c > 0)][(((a) + ((a) > 0)) % (h))]
                    [(((b) + ((b) > 0)) % (h))][alive] -= mod;
              };
            }
    }
    int ans = 0;
    for (int a = 0; a < (h); a++)
      for (int b = 0; b < (h); b++)
        for (int c = 0; c < (h); c++) {
          if (a > 0 || b > 0 || c > 0) {
            ans += dp[n & 1][0][a][b][c];
            if (ans >= mod) ans -= mod;
          };
          {
            ans += dp[n & 1][1][a][b][c];
            if (ans >= mod) ans -= mod;
          };
        }
    printf("%d\n", ans);
  }
  return 0;
}
