#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, m;
  long long dp[2][32][32][32][2], t, j3, ret;
  long long mod = 1000000009;
  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++) {
            t = dp[i & 1][j0][j1][j2][k];
            if (!t) continue;
            dp[i & 1][j0][j1][j2][k] = 0;
            t %= mod;
            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;
}
