#include <bits/stdc++.h>
using namespace std;
int n, h;
const int mod = 1000000009;
int next(int x) {
  if (x == 0 || x == h - 1)
    return 0;
  else
    return x + 1;
}
int main() {
  cin >> n >> h;
  int d[2][2][32][32][32];
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++)
      for (int k = 0; k <= h; k++)
        for (int l = 0; l <= h; l++)
          for (int m = 0; m <= h; m++) d[i][j][k][l][m] = 0;
  d[0][1][0][0][0] = 4;
  for (int i = 1; i <= n - 1; i++) {
    for (int alive = 0; alive < 2; alive++)
      for (int last1 = 0; last1 < h; last1++)
        for (int last2 = 0; last2 < h; last2++)
          for (int last3 = 0; last3 < h; last3++) {
            d[1][alive][next(last1)][next(last2)][next(last3)] +=
                d[0][alive][last1][last2][last3];
            d[1][alive][next(last1)][next(last2)][next(last3)] %= mod;
            d[1][last1 > 0 || i < h][alive][next(last2)][next(last3)] +=
                d[0][alive][last1][last2][last3];
            d[1][last1 > 0 || i < h][alive][next(last2)][next(last3)] %= mod;
            d[1][last2 > 0 || i < h][next(last1)][alive][next(last3)] +=
                d[0][alive][last1][last2][last3];
            d[1][last2 > 0 || i < h][next(last1)][alive][next(last3)] %= mod;
            d[1][last3 > 0 || i < h][next(last1)][next(last2)][alive] +=
                d[0][alive][last1][last2][last3];
            d[1][last3 > 0 || i < h][next(last1)][next(last2)][alive] %= mod;
          }
    for (int j = 0; j < 2; j++)
      for (int k = 0; k <= h; k++)
        for (int l = 0; l <= h; l++)
          for (int m = 0; m <= h; m++) {
            d[0][j][k][l][m] = d[1][j][k][l][m];
            d[1][j][k][l][m] = 0;
          }
  }
  int res = 0;
  for (int a = 0; a < h; a++)
    for (int b = 0; b < h; b++)
      for (int c = 0; c < h; c++) {
        res = (res + d[0][1][a][b][c]) % mod;
        if (a != 0 || b != 0 || c != 0) res = (res + d[0][0][a][b][c]) % mod;
      }
  cout << res << endl;
}
