小红的好排列

import java.util.*;

public class Main {
    static final int MOD = (int) 1e9 + 7;
    static int maxN = (int) 1e6;
    static long[] fact;
    static long[] finv;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        preprocess(maxN);

        int c = n / 3;
        int m = c;

        if (c > n / 2) {
            System.out.println(0);
            return;
        }

        int s = (n / 2) - c;
        if (m < s) {
            System.out.println(0);
            return;
        }

        int k = 2 * c - (n / 2);
        if (k < 0) {
            System.out.println(0);
            return;
        }

        int nc = n - c;
        int nm = n - m;
        int ck = c - k;
        int mk = m - k;

        long ans = comb(c, k);
        ans = ans * comb(nc, s) % MOD;
        ans = ans * (perm(m, k) * perm(nm, ck) % MOD) % MOD;
        ans = ans * (perm(mk, s) * fact[n / 2] % MOD) % MOD;

        System.out.println(ans);
    }

    static void preprocess(int n) {
        fact = new long[n + 1];
        finv = new long[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = fact[i - 1] * i % MOD;
        }
        finv[n] = pow(fact[n], MOD - 2);
        for (int i = n - 1; i >= 0; i--) {
            finv[i] = finv[i + 1] * (i + 1) % MOD;
        }
    }

    static long pow(long a, long b) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) != 0) {
                res = res * a % MOD;
            }
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }

    static long comb(int a, int b) {
        if (a < 0 || b < 0 || a < b) return 0;
        return fact[a] * finv[b] % MOD * finv[a - b] % MOD;
    }

    static long perm(int a, int b) {
        if (a < 0 || b < 0 || a < b) return 0;
        return fact[a] * finv[a - b] % MOD;
    }
}