#include <bits/stdc++.h>
using namespace std;
int n, h;
int f[1001][65536] = {0};
inline void upd(int &x, int v) {
  x = (x + v >= 1000000009 ? x + v - 1000000009 : x + v);
}
int main() {
  scanf("%d%d", &n, &h);
  f[0][((0) << 11 | (0) << 6 | (0) << 1 | (0))] = 1;
  int tmp;
  for (int t = 0; t < n; t++)
    for (int a = 0; a <= h; a++)
      for (int b = a; b <= h; b++)
        for (int c = b; c <= h; c++) {
          if (tmp = f[t][((a) << 11 | (b) << 6 | (c) << 1 | (0))]) {
            if (c == h - 1) {
              upd(f[t + 1][((0) << 11 | (a + 1) << 6 | (b + 1) << 1 | (1))],
                  tmp);
              upd(f[t + 1][((0) << 11 | (1) << 6 | (b + 1) << 1 | (1))], tmp);
              upd(f[t + 1][((0) << 11 | (1) << 6 | (a + 1) << 1 | (1))], tmp);
            } else {
              upd(f[t + 1][((a + 1) << 11 | (b + 1) << 6 | (c + 1) << 1 | (0))],
                  tmp);
              upd(f[t + 1][((1) << 11 | (b + 1) << 6 | (c + 1) << 1 | (0))],
                  tmp);
              upd(f[t + 1][((1) << 11 | (a + 1) << 6 | (c + 1) << 1 | (0))],
                  tmp);
            }
            if (b == h - 1) {
              upd(f[t + 1][((0) << 11 | (1) << 6 | (a + 1) << 1 | (1))], tmp);
            } else
              upd(f[t + 1][((1) << 11 | (a + 1) << 6 | (b + 1) << 1 | (0))],
                  tmp);
          }
          if (tmp = f[t][((a) << 11 | (b) << 6 | (c) << 1 | (1))]) {
            int k = 1;
            if (c == h)
              k++;
            else
              upd(f[t + 1][((0) << 11 | (a == h ? h : a + 1) << 6 |
                            (b == h ? h : b + 1) << 1 | (1))],
                  tmp);
            if (b == h)
              k++;
            else
              upd(f[t + 1][((0) << 11 | (a == h ? h : a + 1) << 6 |
                            (c == h ? h : c + 1) << 1 | (1))],
                  tmp);
            if (a == h)
              k++;
            else
              upd(f[t + 1][((0) << 11 | (b == h ? h : b + 1) << 6 |
                            (c == h ? h : c + 1) << 1 | (1))],
                  tmp);
            if (k == 4) continue;
            upd(f[t + 1]
                 [((a == h ? h : a + 1) << 11 | (b == h ? h : b + 1) << 6 |
                   (c == h ? h : c + 1) << 1 | (1))],
                1ll * tmp * k % 1000000009);
          }
        }
  int ans = 0;
  for (int a = 0; a <= h; a++)
    for (int b = a; b <= h; b++)
      for (int c = b; c <= h; c++) {
        upd(ans, f[n][((a) << 11 | (b) << 6 | (c) << 1 | (0))]);
        if (a != h) upd(ans, f[n][((a) << 11 | (b) << 6 | (c) << 1 | (1))]);
      }
  printf("%d\n", ans);
  return 0;
}
