#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1007;
const int MOD = 1e9 + 9;
int n, h, dp[maxn][2][33][33][33], t, ans;
int Incert(int &tmp) { tmp = (tmp + t) % MOD; }
int main() {
  scanf("%d%d", &n, &h);
  dp[0][0][0][0][0] = 1;
  for (int i = 1; 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++) {
            t = dp[i - 1][a][b][c][d];
            Incert(dp[i][a < 1 ? 0 : 1][b < h ? b + 1 : h][c < h ? c + 1 : h]
                     [d < h ? d + 1 : h]);
            Incert(dp[i][b < h ? 0 : 1][c < h ? c + 1 : h][d < h ? d + 1 : h]
                     [a < 1 ? a + 1 : h]);
            Incert(dp[i][c < h ? 0 : 1][d < h ? d + 1 : h][a < 1 ? a + 1 : h]
                     [b < h ? b + 1 : h]);
            Incert(dp[i][d < h ? 0 : 1][a < 1 ? a + 1 : h][b < h ? b + 1 : h]
                     [c < h ? c + 1 : h]);
          }
        }
      }
    }
  }
  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++) {
          t = dp[n][a][b][c][d];
          if (a < 1 || b < h || c < h || d < h) {
            Incert(ans);
          }
        }
      }
    }
  }
  printf("%d", ans);
}
