题解 | 小红的好排列

import java.util.Scanner;

public class Main {

    static long mod = 1000000007;

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

        int n_3 = n / 3;
        int n_2 = n / 2;

        if (n < 4) {
            System.out.println(0);
            return;
        }

        // 预计算阶乘（用于 C(n,k)）
        long[] fact = new long[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = fact[i - 1] * i % mod;
        }

        int num_overlap = 2 * n_3 - n_2;
        long pc1 = C(n_3, num_overlap, fact);
        long pc2 = (C(n_3, num_overlap, fact) * fact[num_overlap]) % mod;

        long pc3 = P(n - n_3, n_3 - num_overlap);
        long pc4 = fact[n - n_3];
        long res = ((((pc1 * pc2) % mod) * pc3) % mod) * pc4 % mod;
        System.out.println(res % mod);
    }

    // 排列数 P(n, k) = n! / (n-k)!
    public static long P(int n, int k) {
        if (k < 0 || k > n) return 0;
        if (k == 0) return 1;
        long res = 1;
        for (int i = n - k + 1; i <= n; i++) {
            res = res * i % mod;
        }
        return res;
    }

    // 快速幂
    public static long pow(long a, long b) {
        long res = 1;
        while (b > 0) {
            if (b % 2 == 1) {
                res = res * a % mod;
            }
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }

    // 模逆元（费马小定理）
    public static long inv(long a) {
        return pow(a, mod - 2);
    }

    // 组合数 C(n, k) = n! / (k! * (n-k)!)
    public static long C(int n, int k, long[] fact) {
        if (k < 0 || k > n) return 0;
        if (k == 0 || k == n) return 1;
        long numerator = fact[n];
        long denominator = fact[k] * fact[n - k] % mod;
        return numerator * inv(denominator) % mod;
    }
}