#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000009;
int n, h;
int memo[1024][32][32][32][2];
int calc(int u, int d1, int d2, int d3, int sat) {
  if (u == n + 1) {
    if (d1 <= h or d2 <= h or d3 <= h or !sat) return 1;
    return 0;
  }
  int &ret = memo[u][d1][d2][d3][sat];
  if (ret != -1) return ret;
  int a, b, c, d;
  a = (sat ? 31 : 1);
  b = d1;
  c = d2;
  d = d3;
  int tot = 0;
  int na = (a > h ? 31 : 1), nb = (b + 1 <= h ? b + 1 : 31),
      nc = (c + 1 <= h ? c + 1 : 31), nd = (d + 1 <= h ? d + 1 : 31);
  tot = (tot + calc(u + 1, nb, nc, nd, (na == 31 ? 1 : 0))) % MOD;
  na = (a + 1 <= h ? a + 1 : 31);
  nb = (b > h ? 31 : 1);
  nc = (c + 1 <= h ? c + 1 : 31);
  nd = (d + 1 <= h ? d + 1 : 31);
  tot = (tot + calc(u + 1, na, nc, nd, (nb == 31 ? 1 : 0))) % MOD;
  na = (a + 1 <= h ? a + 1 : 31);
  nb = (b + 1 <= h ? b + 1 : 31);
  nc = (c > h ? 31 : 1);
  nd = (d + 1 <= h ? d + 1 : 31);
  tot = (tot + calc(u + 1, na, nb, nd, (nc == 31 ? 1 : 0))) % MOD;
  na = (a + 1 <= h ? a + 1 : 31);
  nb = (b + 1 <= h ? b + 1 : 31);
  nc = (c + 1 <= h ? c + 1 : 31);
  nd = (d > h ? 31 : 1);
  tot = (tot + calc(u + 1, na, nb, nc, (nd == 31 ? 1 : 0))) % MOD;
  return ret = tot;
}
int main() {
  memset(memo, -1, sizeof(memo));
  scanf("%d %d", &n, &h);
  printf("%d\n", calc(1, 1, 1, 1, 0));
  return 0;
}
