#include <bits/stdc++.h>
const int mod = 1000000009;
int dp[2][2][31][31][31], n, h;
void INC(int &a, int b) {
  a += b;
  if (a >= mod) a -= mod;
}
int main() {
  scanf("%d%d", &n, &h);
  dp[0][1][0][0][0] = 1;
  int s = 0, _tmp, x3;
  int f0, f1, f2, f3;
  for (int i = 0; i < n; i++) {
    s ^= 1;
    for (int x0 = 0; x0 < h + 1; x0++)
      for (int x1 = 0; x1 < h + 1; x1++)
        for (int x2 = 0; x2 < h + 1; x2++)
          for (int k = 0; k < 2; k++) {
            int &tmp = dp[s ^ 1][k][x0][x1][x2];
            _tmp = tmp;
            tmp = 0;
            f3 = k ? 1 : h;
            f0 = (x0 == h ? h : x0 + 1);
            f1 = (x1 == h ? h : x1 + 1);
            f2 = (x2 == h ? h : x2 + 1);
            INC(dp[s][x0 < h][f1][f2][f3], _tmp);
            INC(dp[s][x1 < h][f0][f2][f3], _tmp);
            INC(dp[s][x2 < h][f0][f1][f3], _tmp);
            INC(dp[s][k][f0][f1][f2], _tmp);
          }
  }
  int ans = 0;
  for (int x0 = 0; x0 < h + 1; x0++)
    for (int x1 = 0; x1 < h + 1; x1++)
      for (int x2 = 0; x2 < h + 1; x2++)
        for (int alive = 0; alive < 2; alive++)
          if (x0 < h || x1 < h || x2 < h || alive)
            INC(ans, dp[s][alive][x0][x1][x2]);
  printf("%d\n", ans);
  return 0;
}
