import java.util.Scanner;

public class Main {

static final int MOD = 1000000009;
public static int N;
static int [] size;
static long [] jie;
static long [] ni;
public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    N = scanner.nextInt();
    size = new int[N+1];
    jie = new long[N+1];
    ni = new long[N+1];
    initsize();
    initjie();
    System.out.println(dp());

}

private static long dp() {
    long [] d = new long[N+1];
    for (int i = N; i >= 1; i--) {
        if (2*i+1<=N) { //既有左子树，又有右子树
            d[i] = c(size[i]-1,size[2*i])*d[2*i] % MOD *d[2*i+1] % MOD;
        }else if (2*i<=N) {//只有左子树
            d[i] = c(size[i]-1,size[2*i])*d[2*i] % MOD;
        }else {//无子树
            d[i] = 1;
        }

    }
    return d[1];
}

private static long c(int n, int r) {
    return jie[n] * ni[r] % MOD * ni[n-r] % MOD;
}

private static void initjie() {
    jie[0] = 1;
    ni[0] = 1;
    for (int i = 1; i < N; i++) {
        jie[i] = jie[i-1] * i % MOD;
        ni[i] = pow(jie[i], MOD-2);

    }

}
private static void initsize() {
    for (int i = N; i >= 1; i--) {
        size[i] = (2*i <= N ? size[2*i]:0) + (2*i+1 <= N ? size[2*i+1]:0) + 1;
    }

}

private static long pow(long a,int n) {
    if (a==0) {
        return 0;
    }
    long ans = 1;
    long x = a;
    while (n>0) {
        if ((n & 1) == 1) {
            ans = ans * x % MOD;
        }
        n >>= 1;
        x = x*x%MOD;
    }
    return ans;
}

}