#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;
}
/*#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;

bool chmin(int &x, int y) {return x > y ? x = y, 1 : 0;}

typedef pair <int, int> pii;
typedef pair <pii, int> ppi;

int n;
int a[30];
vector <ppi> P, Q;

void dfs(int *bg, int *ed, int x, int y, int mask, vector <ppi> &P) {
	if (bg == ed) {
		P.push_back(mp(mp(x, y), mask));
		return ;
	}
	dfs(bg + 1, ed, x - *bg, y, mask * 3 + 0, P);
	dfs(bg + 1, ed, x + *bg, y - *bg, mask * 3 + 1, P);
	dfs(bg + 1, ed, x, y + *bg, mask * 3 + 2, P);
}

namespace BIT {
	pii T[2000010];
	void Clear() {
		; for (int i = 0; i <= 2000005; i++) T[i] = mp(0x3f3f3f3f, -1);
	}
	void Modify(int x, pii v) {
		while (x <= 2000005) T[x] = min(T[x], v), x += x & -x;
	}
	pii Query(int x) {
		pii res = mp(0x3f3f3f3f, -1);
		while (x) res = min(res, T[x]), x -= x & -x;
		return res;
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	int p = n / 2, q = n - p;
	for (int i = p - 1; i >= 0; i--) {
		ways[i] = wP % 3 + 1, wP /= 3;
	}
	for (int i = n - 1; i >= p; i--) {
		ways[i] = wQ % 3 + 1, wQ /= 3;
	}
	for (int i = 0; i < n; i++) {
		printf("%d ", ways[i]);
	}
	printf("\n");
	return 0;
}*/