#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000000 + 9;
int f[2][31][31][31][31], n, lim;
inline void inc(int& a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
}
int ps[4], pt[4];
int main() {
  scanf("%d%d", &n, &lim);
  int cur = 0;
  f[0][0][0][0][0] = 1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= lim; j++)
      for (int k = 0; k <= j; k++)
        for (int s = 0; s <= k; s++)
          for (int g = 0; g <= s; g++) f[cur ^ 1][j][k][s][g] = 0;
    for (ps[0] = 0; ps[0] <= lim; ps[0]++)
      for (ps[1] = 0; ps[1] <= ps[0]; ps[1]++)
        for (ps[2] = 0; ps[2] <= ps[1]; ps[2]++)
          for (ps[3] = 0; ps[3] <= ps[2]; ps[3]++)
            if (f[cur][ps[0]][ps[1]][ps[2]][ps[3]]) {
              for (int fi = 0; fi < 4; fi++) {
                pt[0] = min(lim, ps[0] + 1);
                pt[1] = min(lim, ps[1] + 1);
                pt[2] = min(lim, ps[2] + 1);
                pt[3] = min(lim, ps[3] + 1);
                if (ps[fi] != lim) {
                  pt[fi] = 0;
                  for (int t = fi; t < 3; t++) swap(pt[t], pt[t + 1]);
                }
                inc(f[cur ^ 1][pt[0]][pt[1]][pt[2]][pt[3]],
                    f[cur][ps[0]][ps[1]][ps[2]][ps[3]]);
              }
            }
    cur ^= 1;
  }
  int ans = 0;
  for (int i = 0; i <= lim; i++)
    for (int j = 0; j <= i; j++)
      for (int k = 0; k <= j; k++)
        for (int g = 0; g <= k; g++)
          if (g != lim) inc(ans, f[cur][i][j][k][g]);
  printf("%d\n", ans);
  return 0;
}
