#include <bits/stdc++.h>
using namespace std;
int f[1005][2][32][32][32], n, h, ans = 0;
void add(int &x, int y) {
  x += y;
  if (x > 1000000009) x -= 1000000009;
}
int main() {
  scanf("%d%d", &n, &h);
  f[1][1][0][0][0] = 4;
  for (int i = 1; i < n; i++) {
    for (int j0 = 0; j0 <= 1; j0++)
      for (int j1 = 0; j1 < h; j1++)
        for (int j2 = 0; j2 < h; j2++)
          for (int j3 = 0; j3 < h; j3++) {
            int J1 = j1, J2 = j2, J3 = j3;
            if (J1) J1 = (J1 + 1) % h;
            if (J2) J2 = (J2 + 1) % h;
            if (J3) J3 = (J3 + 1) % h;
            add(f[i + 1][j0][J1][J2][J3], f[i][j0][j1][j2][j3]);
            add(f[i + 1][j1 > 0 || i < h][j0][J2][J3], f[i][j0][j1][j2][j3]);
            add(f[i + 1][j2 > 0 || i < h][J1][j0][J3], f[i][j0][j1][j2][j3]);
            add(f[i + 1][j3 > 0 || i < h][J1][J2][j0], f[i][j0][j1][j2][j3]);
          }
  }
  for (int j1 = 0; j1 < h; j1++)
    for (int j2 = 0; j2 < h; j2++)
      for (int j3 = 0; j3 < h; j3++) {
        add(ans, f[n][1][j1][j2][j3]);
        if (j1 + j2 + j3 != 0) add(ans, f[n][0][j1][j2][j3]);
      }
  printf("%d\n", ans);
  return 0;
}
