#include <bits/stdc++.h>
using namespace std;
int dp[2][2][32][32][32];
int n, h;
int main() {
  ios ::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> h;
  dp[0][0][0][0][0] = 1;
  for (int i = 1; i <= n; i++) {
    int now = i % 2;
    memset(dp[now], 0, sizeof(dp[now]));
    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++) {
            int val = dp[1 - now][a][b][c][d];
            (dp[now][a][min(b + 1, h)][min(c + 1, h)][min(d + 1, h)] += val) %=
                1000000009;
            (dp[now][b < h ? 0 : 1][min(c + 1, h)][min(d + 1, h)]
               [a < 1 ? 1 : h] += val) %= 1000000009;
            (dp[now][c < h ? 0 : 1][min(d + 1, h)][a < 1 ? 1 : h]
               [min(b + 1, h)] += val) %= 1000000009;
            (dp[now][d < h ? 0 : 1][a < 1 ? 1 : h][min(b + 1, h)]
               [min(c + 1, h)] += val) %= 1000000009;
          }
  }
  int res = 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 (a != 1 || b != h || c != h || d != h)
            (res += dp[n % 2][a][b][c][d]) %= 1000000009;
  cout << res;
  return 0;
}
