#pragma GCC optimize("Ofast, unroll-loops, inline")
#include <cstdio>
#define ll long long
#define mo 1000000009

using namespace std;

int n, m;
ll jc[61], inv[61], p[61], f[21][61];
inline ll C(int n, int m) {
    if (n < m)
        return 0;

    if (m < 0)
        return 0;

    return jc[n] * inv[m] % mo * inv[n - m] % mo;
}

ll ksm(ll x, ll y) {
    ll re = 1;

    while (y) {
        if (y & 1)
            re = re * x % mo;

        x = x * x % mo;
        y >>= 1;
    }

    return re;
}


int main() {
    scanf("%d %d", &n, &m);
	jc[0] = 1;

    for (int i = 1; i <= m + 1; i++)
        jc[i] = jc[i - 1] * i % mo;

    inv[m + 1] = ksm(jc[m + 1], mo - 2);

    for (int i = m; i >= 0; i--)
        inv[i] = inv[i + 1] * (i + 1) % mo;

    int on = (m + 1) / 2, jn = (m + 2) / 2;

    for (int k = 0; k <= m + 1; k++) {
        for (int i = 0; i <= on; i += 2) {
            p[k] = (p[k] + C(on, i) * C(jn, k - i) % mo) % mo;
        }
    }
    f[20][0] = 1;
    int need = n - m;

    for (int i = 19; i >= 0; i--) {
        int hv = (need >> i) & 1;

        for (int j = 0; j <= m + 1; j++)
            for (int k = 0; k <= m + 1; k++) {
                int to = 2 * j + hv - k;

                if (to < 0 || to > m + 1)
                    continue;

                f[i][to] = (f[i][to] + f[i + 1][j] * p[k] % mo) % mo;
            }
    }

    ll ans = 1;

    for (int i = n - m + 1; i <= n; i++)
        ans = ans * i % mo;

    ans = ans * inv[m];
    printf("%lld", (ans - f[0][0] + mo) % mo);
    return 0;
}