#include <bits/stdc++.h>
using namespace std;
long long dp[2][32][32][32][2], ret, j3, MOD = 1000000009;
int main() {
  int n, m;
  cin >> n >> m;
  dp[0][0][0][0][1] = 1;
  for (int i = 0; i < n; ++i)
    for (int j0 = 0; j0 <= m; ++j0)
      for (int j1 = 0; j1 <= m; ++j1)
        for (int j2 = 0; j2 <= m; ++j2)
          for (int k = 0; k < 2; ++k) {
            long long t = dp[i & 1][j0][j1][j2][k];
            t %= MOD;
            dp[i & 1][j0][j1][j2][k] = 0;
            if (!t) continue;
            if (k)
              j3 = 1;
            else
              j3 = m;
            dp[i & 1 ^ 1][min(m, j1 + 1)][min(m, j2 + 1)][j3][j0 < m] += t;
            dp[i & 1 ^ 1][min(m, j0 + 1)][min(m, j2 + 1)][j3][j1 < m] += t;
            dp[i & 1 ^ 1][min(m, j0 + 1)][min(m, j1 + 1)][j3][j2 < m] += t;
            dp[i & 1 ^ 1][min(m, j0 + 1)][min(m, j1 + 1)][min(m, j2 + 1)][k] +=
                t;
          }
  for (int j0 = 0; j0 <= m; ++j0)
    for (int j1 = 0; j1 <= m; ++j1)
      for (int j2 = 0; j2 <= m; ++j2)
        for (int k = 0; k < 2; ++k)
          if (j0 < m || j1 < m || j2 < m || k)
            ret = (ret + dp[n & 1][j0][j1][j2][k]) % MOD;
  cout << ret;
  return 0;
}
