#include <bits/stdc++.h>
using namespace std;
const int mod = (int)1e9 + 9;
int dp[1003][2][33][33][33], t, ans;
void add(int &x, int y) {
  x += y;
  if (x >= mod) x -= mod;
}
int n, h, a, b, c;
int f(int a) {
  if (!a || a == h - 1) return 0;
  return a + 1;
}
int main() {
  int i, g;
  scanf("%d%d", &n, &h);
  dp[1][1][0][0][0] = 4;
  for (i = 1; i < n; i++)
    for (g = 0; g <= 1; g++)
      for (a = 0; a < h; a++)
        for (b = 0; b < h; b++)
          for (c = 0; c < h; c++) {
            if ((t = dp[i][g][a][b][c])) {
              int aa = f(a), bb = f(b), cc = f(c);
              add(dp[i + 1][g][aa][bb][cc], t);
              add(dp[i + 1][a > 0 || i < h][g][bb][cc], t);
              add(dp[i + 1][b > 0 || i < h][aa][g][cc], t);
              add(dp[i + 1][c > 0 || i < h][aa][bb][g], t);
            }
          }
  for (g = 0; g <= 1; g++)
    for (a = 0; a < h; a++)
      for (b = 0; b < h; b++)
        for (c = 0; c < h; c++)
          if (a + b + c || g) add(ans, dp[n][g][a][b][c]);
  printf("%d\n", ans);
  return 0;
}
