#include <bits/stdc++.h>
using namespace std;
int a[2][2][31][31][31], n, m, ans;
inline void Add(int &x, int y) {
  x += y;
  x -= x < 1000000009 ? 0 : 1000000009;
}
int main() {
  cin >> n >> m;
  a[0][1][m][m][m] = 1;
  for (int t = 1, tt = 1; t <= n; t++, tt ^= 1, memset(a[tt], 0, sizeof(a[tt])))
    for (int i = 0; i < 2; i++)
      for (int j = 0; j <= m; j++)
        for (int k = 0; k <= m; k++)
          for (int l = 0; l <= m; l++) {
            if (!a[tt ^ 1][i][j][k][l]) continue;
            int i0 = i ? m - 1 : 0, j0 = j ? j - 1 : 0, k0 = k ? k - 1 : 0,
                l0 = l ? l - 1 : 0;
            Add(a[tt][i][j0][k0][l0], a[tt ^ 1][i][j][k][l]);
            Add(a[tt][j > 0][k0][l0][i0], a[tt ^ 1][i][j][k][l]);
            Add(a[tt][k > 0][j0][l0][i0], a[tt ^ 1][i][j][k][l]);
            Add(a[tt][l > 0][j0][k0][i0], a[tt ^ 1][i][j][k][l]);
          }
  for (int i = 0; i <= 1; i++)
    for (int j = 0; j <= m; j++)
      for (int k = 0; k <= m; k++)
        for (int l = 0; l <= m; l++)
          if (i || k || j || l) Add(ans, a[n & 1][i][j][k][l]);
  cout << ans << endl;
  return 0;
}
