#include <bits/stdc++.h>
using namespace std;
int f, dp[2][2][30][30][30], ans;
void add(int &u, int x) {
  u += x;
  if (u >= 1000000009) u -= 1000000009;
}
int main() {
  int n, h;
  scanf("%d %d", &n, &h);
  dp[f][1][0][0][0] = 4;
  for (int i = 1, F; i < n; i++, f = F) {
    F = f ^ 1;
    for (int j = 2; j--;) {
      for (int a = h; a--;) {
        for (int b = h; b--;) {
          for (int c = h; c--;) {
            dp[F][j][a][b][c] = 0;
          }
        }
      }
    }
    bool ok = i < h;
    for (int j = 2; j--;) {
      for (int a = h; a--;) {
        int A = a ? (a + 1) % h : 0;
        for (int b = h; b--;) {
          int B = b ? (b + 1) % h : 0;
          for (int c = h; c--;) {
            int C = c ? (c + 1) % h : 0;
            int val = dp[f][j][a][b][c];
            add(dp[F][j][A][B][C], val);
            add(dp[F][ok || a > 0][j][B][C], val);
            add(dp[F][ok || b > 0][A][j][C], val);
            add(dp[F][ok || c > 0][A][B][j], val);
          }
        }
      }
    }
  }
  for (int a = h; a--;) {
    for (int b = h; b--;) {
      for (int c = h; c--;) {
        add(ans, dp[f][1][a][b][c]);
        if (a || b || c) add(ans, dp[f][0][a][b][c]);
      }
    }
  }
  printf("%d", ans);
}
