#include <bits/stdc++.h>
using namespace std;
long long ans, i, N, H, alive, last1, last2, last3, a, b, c;
long long A[2][32][32][32], B[2][32][32][32];
int main() {
  cin >> N >> H;
  A[1][0][0][0] = 4;
  for (i = 1; i < N; i++) {
    for (alive = 0; alive < 2; alive++)
      for (last1 = 0; i - last1 > 0 && last1 < H; last1++)
        for (last2 = 0; i - last2 > 0 && last2 < H; last2++)
          for (last3 = 0; i - last3 > 0 && last3 < H; last3++) {
            if (last1 == 0 || last1 == H - 1)
              a = 0;
            else
              a = last1 + 1;
            if (last2 == 0 || last2 == H - 1)
              b = 0;
            else
              b = last2 + 1;
            if (last3 == 0 || last3 == H - 1)
              c = 0;
            else
              c = last3 + 1;
            B[alive][a][b][c] += A[alive][last1][last2][last3];
            B[alive][a][b][c] %= 1000000009;
            B[last1 > 0 || i < H][alive][b][c] += A[alive][last1][last2][last3];
            B[last1 > 0 || i < H][alive][b][c] %= 1000000009;
            B[last2 > 0 || i < H][a][alive][c] += A[alive][last1][last2][last3];
            B[last2 > 0 || i < H][a][alive][c] %= 1000000009;
            B[last3 > 0 || i < H][a][b][alive] += A[alive][last1][last2][last3];
            B[last3 > 0 || i < H][a][b][alive] %= 1000000009;
          }
    for (alive = 0; alive < 2; alive++)
      for (last1 = 0; last1 < H; last1++)
        for (last2 = 0; last2 < H; last2++)
          for (last3 = 0; last3 < H; last3++) {
            A[alive][last1][last2][last3] = B[alive][last1][last2][last3];
            B[alive][last1][last2][last3] = 0;
          }
  }
  for (a = 0; a < H; a++)
    for (b = 0; b < H; b++)
      for (c = 0; c < H; c++) ans = (ans + A[1][a][b][c]) % 1000000009;
  for (a = 0; a < H; a++)
    for (b = 0; b < H; b++)
      for (c = 0; c < H; c++)
        if (a > 0 || b > 0 || c > 0) ans = (ans + A[0][a][b][c]) % 1000000009;
  cout << ans << endl;
}
