#include <bits/stdc++.h>
using namespace std;
int n, h;
int f[1010][2][33][33][33];
void add(int &a, int b) {
  a += b;
  if (a >= 1000000009) a -= 1000000009;
}
int main() {
  cin >> n >> h;
  int cur = 0, lst = 1;
  f[0][1][0][0][0] = 1;
  for (int i = 0; i < n; i++)
    for (int a = 0; a < 2; a++)
      for (int b = 0; b <= h; b++)
        for (int c = 0; c <= h; c++)
          for (int d = 0; d <= h; d++) {
            int tmp = f[i][a][b][c][d];
            if (!tmp) continue;
            add(f[i + 1][a][b < h ? b + 1 : b][c < h ? c + 1 : c]
                 [d < h ? d + 1 : d],
                tmp);
            add(f[i + 1][b < h][a == 0 ? h : 1][c < h ? c + 1 : c]
                 [d < h ? d + 1 : d],
                tmp);
            add(f[i + 1][c < h][b < h ? b + 1 : b][a == 0 ? h : 1]
                 [d < h ? d + 1 : d],
                tmp);
            add(f[i + 1][d < h][b < h ? b + 1 : b][c < h ? c + 1 : c]
                 [a == 0 ? h : 1],
                tmp);
          }
  int ans = 0;
  for (int a = 0; a < 2; a++)
    for (int b = 0; b <= h; b++)
      for (int c = 0; c <= h; c++)
        for (int d = 0; d <= h; d++)
          if (a || b < h || c < h || d < h) add(ans, f[n][a][b][c][d]);
  cout << ans << endl;
  return 0;
}
