#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ui unsigned int
#define ull unsigned ll
#define pii pair<int,int>
#define pll pair<ll,ll>
#define db double
#define mp make_pair
#define X first
#define Y second
#define vi vector<int>
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,b,a) for(int i=(b);i>=(a);--i)
#define rep0(i,a,b) for(int i=(a);i<(b);++i)
#define fore(i,a) for(int i=0;i<(a).size();++i)
#define gc getchar
inline ll rd()
{
    ll x = 0;
    char c = gc();

    while (!isdigit(c))
        c = gc();

    while (isdigit(c))
        x = x * 10 + c - 48, c = gc();

    return x;
}
const int N = 70, P = 1e9 + 9;
int n, m, fac[N], ifac[N], f[N][N], g[N];
inline int pw(int a, int b)
{
    int r = 1;

    for (; b; b >>= 1, a = 1ll * a * a % P)
        if (b & 1)
            r = 1ll * r * a % P;

    return r;
}
inline int C(int a, int b)
{
    return a >= b && b >= 0 ? 1ll * fac[a] * ifac[b] % P * ifac[a - b] % P : 0;
}
inline int sol(int n, int m)
{
    int o = m >> 1, e = m - o;
    f[18][0] = 1;

    rep(i, 0, m)for (int j = 0; j <= i; j += 2)
        g[i] = (g[i] + 1ll * C(o, j) * C(e, i - j)) % P;

    per(i, 17, 0)rep(j, 0, m)if (f[i + 1][j])
    {
        int t = (j * 2) + (n >> i & 1);

        for (int k = max(0, t - m); k <= m && k <= t; k++)
            f[i][t - k] = (f[i][t - k] + 1ll * f[i + 1][j] * g[k]) % P;
    }

    return f[0][0];
}
int main()
{
    n = rd();
    m = rd();
    fac[0] = 1;
    rep0(i, 1, N)fac[i] = 1ll * fac[i - 1] * i % P;
    ifac[N - 1] = pw(fac[N - 1], P - 2);
    per(i, N - 1, 1)ifac[i - 1] = 1ll * ifac[i] * i % P;
    int s = ifac[m];
    per(i, n, n - m + 1)s = 1ll * s * i % P;
    printf("%d\n", (s + P - sol(n - m, m + 1)) % P);
    return 0;
}