#include <bits/stdc++.h>
using namespace std;
const int Maxn = 1005, Maxh = 33, mod = 1000000009;
int n, h, ans = 0;
int f[Maxn][Maxh][Maxh][Maxh][2];
inline void add(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
int main() {
  cin >> n >> h;
  f[1][1][1][1][1] = 4;
  for (int i = 1; i < n; i++)
    for (int x = 1; x <= h; x++)
      for (int y = 1; y <= h; y++)
        for (int z = 1; z <= h; z++) {
          int X = min(h, x + 1), Y = min(h, y + 1), Z = min(h, z + 1);
          for (int k = 0; k < 2; k++) {
            add(f[i + 1][X][Y][Z][k], f[i][x][y][z][k]);
            add(f[i + 1][Y][Z][k ? 1 : h][x < h], f[i][x][y][z][k]);
            add(f[i + 1][Z][k ? 1 : h][X][y < h], f[i][x][y][z][k]);
            add(f[i + 1][k ? 1 : h][X][Y][z < h], f[i][x][y][z][k]);
          }
        }
  for (int x = 1; x <= h; x++)
    for (int y = 1; y <= h; y++)
      for (int z = 1; z <= h; z++) {
        add(ans, f[n][x][y][z][1]);
        if (x + y + z < 3 * h) add(ans, f[n][x][y][z][0]);
      }
  cout << ans << endl;
  return 0;
}
