#include <bits/stdc++.h>
using namespace std;
int n, h, dp[1003][2][31][31][31], val;
void add(int &a) {
  if ((a += val) >= 1000000009) a -= 1000000009;
}
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 <= 1; a++)
      for (int b = 0; b <= h; b++)
        for (int c = 0; c <= h; c++)
          for (int d = 0; d <= h; d++)
            if (val = dp[i - 1][a][b][c][d]) {
              add(dp[i][a < 1 ? 0 : 1][b < h ? b + 1 : h][c < h ? c + 1 : h]
                    [d < h ? d + 1 : h]);
              add(dp[i][b < h ? 0 : 1][c < h ? c + 1 : h][d < h ? d + 1 : h]
                    [a < 1 ? a + 1 : h]);
              add(dp[i][c < h ? 0 : 1][d < h ? d + 1 : h][a < 1 ? a + 1 : h]
                    [b < h ? b + 1 : h]);
              add(dp[i][d < h ? 0 : 1][a < 1 ? a + 1 : h][b < h ? b + 1 : h]
                    [c < h ? c + 1 : h]);
            }
  int ans = 0;
  for (int a = 0; a <= 1; a++)
    for (int b = 0; b <= h; b++)
      for (int c = 0; c <= h; c++)
        for (int d = 0; d <= h; d++)
          if ((val = dp[n][a][b][c][d]) && (a < 1 || b < h || c < h || d < h))
            (ans += val) %= 1000000009;
  printf("%d\n", ans);
  return 0;
}
