#include <bits/stdc++.h>
using namespace std;
const int MAXH = 31;
const int MOD = 1000000009;
int dp[2][2][MAXH][MAXH][MAXH];
int main() {
  int n, h;
  scanf("%d%d", &n, &h);
  int cur = 0, pre = 1;
  dp[cur][1][1][1][1] = 4;
  int i, o, a, b, c, aa, bb, cc;
  for (i = 2; i <= n; ++i) {
    swap(cur, pre);
    fill(dp[cur][0][0][0], dp[cur + 1][0][0][0], 0);
    for (o = 0; o < 2; ++o) {
      for (a = 0, aa = 0; a <= h; aa = (++a + 1) % (h + 1)) {
        for (b = 0, bb = 0; b <= h; bb = (++b + 1) % (h + 1)) {
          for (c = 0, cc = 0; c <= h; cc = (++c + 1) % (h + 1)) {
            (dp[cur][o][aa][bb][cc] += dp[pre][o][a][b][c]) %= MOD;
            (dp[cur][aa > 0][o][bb][cc] += dp[pre][o][a][b][c]) %= MOD;
            (dp[cur][bb > 0][aa][o][cc] += dp[pre][o][a][b][c]) %= MOD;
            (dp[cur][cc > 0][aa][bb][o] += dp[pre][o][a][b][c]) %= MOD;
          }
        }
      }
    }
  }
  int ans = 0;
  for (o = 0; o < 2; ++o) {
    for (a = 0; a <= h; ++a) {
      for (b = 0; b <= h; ++b) {
        for (c = 0; c <= h; ++c) {
          if (o || (a && a < h) || (b && b < h) || (c && c < h)) {
            (ans += dp[cur][o][a][b][c]) %= MOD;
          }
        }
      }
    }
  }
  printf("%d\n", ans);
  return 0;
}
