#include <bits/stdc++.h>
using namespace std;
int n, m;
long long dp[2][32][32][32][32];
int Dp() {
  int cur = 0, s[4];
  dp[cur][0][0][0][0] = 1;
  for (int i = 0; i < n; ++i) {
    for (int a = 0; a <= m + 1; ++a)
      for (int b = a; b <= m + 1; ++b)
        for (int c = b; c <= m + 1; ++c)
          for (int d = c; d <= m + 1; ++d)
            if (dp[cur][a][b][c][d]) {
              int val = dp[cur][a][b][c][d] % 1000000009;
              s[0] = a < m ? 0 : m + 1, s[1] = min(m + 1, b + 1),
              s[2] = min(m + 1, c + 1), s[3] = min(m + 1, d + 1),
              sort(s, s + 4);
              dp[cur ^ 1][s[0]][s[1]][s[2]][s[3]] += val;
              s[0] = b < m ? 0 : m + 1, s[1] = min(m + 1, a + 1),
              s[2] = min(m + 1, c + 1), s[3] = min(m + 1, d + 1),
              sort(s, s + 4);
              dp[cur ^ 1][s[0]][s[1]][s[2]][s[3]] += val;
              s[0] = c < m ? 0 : m + 1, s[1] = min(m + 1, a + 1),
              s[2] = min(m + 1, b + 1), s[3] = min(m + 1, d + 1),
              sort(s, s + 4);
              dp[cur ^ 1][s[0]][s[1]][s[2]][s[3]] += val;
              s[0] = d < m ? 0 : m + 1, s[1] = min(m + 1, a + 1),
              s[2] = min(m + 1, b + 1), s[3] = min(m + 1, c + 1),
              sort(s, s + 4);
              dp[cur ^ 1][s[0]][s[1]][s[2]][s[3]] += val;
              dp[cur][a][b][c][d] = 0;
            }
    cur ^= 1;
  }
  int ans = 0;
  for (int a = 0; a <= m - 1; ++a)
    for (int b = a; b <= m + 1; ++b)
      for (int c = b; c <= m + 1; ++c)
        for (int d = c; d <= m + 1; ++d)
          ans = (ans + dp[cur][a][b][c][d]) % 1000000009;
  return ans;
}
int main() {
  cin >> n >> m;
  cout << Dp() << endl;
  return 0;
}
