Count Valid Sequences | Leetcode 4002 | Number Thoery

class Solution {
    using ll = long long;
    int MOD = 1e9+7;
    vector<int> fact;
    vector<int> inv_fact;

    void calculateFactorial(int& n){
        fact[0] = 1;
        for(int i=1;i<=n;++i)
            fact[i] = (1ll * i * fact[i-1]) % MOD;
    }

    int ModuloBinaryExponentiation(int a,int b){
        ll res = 1;
        while(b>0){
            if(b&1)
                res = (1ll * res * a)%MOD;
            a = (1ll * a * a)%MOD;
            b >>= 1;
        }
        return res;
    }
    void calculateInverseFactorial(int& n){
        inv_fact[0] = 1;
        for(int i=n-1;i>=1;--i)
            inv_fact[i] = (1ll * (i+1) * inv_fact[i+1])%MOD;
    }
    int nCr(int n,int r){
        if(r < 0 || r > n)
            return 0;
        return 1ll * fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD;
    }
public:
    int countValidSequences(int n, int k) {
        //Step-1: Precompute Factorial & Inverse Factorial
        fact = vector<int>(n+1);
        inv_fact = vector<int>(n+1);
        calculateFactorial(n);
        inv_fact[n] = ModuloBinaryExponentiation(fact[n],MOD-2);
        calculateInverseFactorial(n);

        //Step-2: Total +ve Sequence count (Odd + Even) = C(n-1,k-1)
        int total = nCr(n-1,k-1);

        //Step-3: Count total odd sequences = C(((n-k)/2 + k - 1), k-1)
        int odds = 0;
        if((n-k)%2==0){
            int val = (n-k)/2;
            odds = nCr(val+k-1,k-1);
        }
        return (total - odds + MOD) % MOD;
    }
};
/*
//JAVA
class Solution {
    int MOD = 1000000007;
    int[] fact;
    int[] inv_fact;

    void calculateFactorial(int n) {
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) {
            // 1L forces 64-bit multiplication to prevent overflow
            fact[i] = (int) ((1L * i * fact[i - 1]) % MOD);
        }
    }

    int moduloBinaryExponentiation(int a, int b) {
        long res = 1;
        long base = a;
        while (b > 0) {
            if ((b & 1) == 1) {
                res = (res * base) % MOD;
            }
            base = (base * base) % MOD;
            b >>= 1;
        }
        return (int) res;
    }

    void calculateInverseFactorial(int n) {
        inv_fact[0] = 1;
        for (int i = n - 1; i >= 1; --i) {
            inv_fact[i] = (int) ((1L * (i + 1) * inv_fact[i + 1]) % MOD);
        }
    }

    int nCr(int n, int r) {
        if (r < 0 || r > n) {
            return 0;
        }
        long temp = (1L * fact[n] * inv_fact[r]) % MOD;
        return (int) ((temp * inv_fact[n - r]) % MOD);
    }

    public int countValidSequences(int n, int k) {
        // Step-1: Precompute Factorial & Inverse Factorial
        fact = new int[n + 1];
        inv_fact = new int[n + 1];
        
        calculateFactorial(n);
        inv_fact[n] = moduloBinaryExponentiation(fact[n], MOD - 2);
        calculateInverseFactorial(n);

        // Step-2: Total +ve Sequence count (Odd + Even) = C(n-1,k-1)
        int total = nCr(n - 1, k - 1);

        // Step-3: Count total odd sequences = C(((n-k)/2 + k - 1), k-1)
        int odds = 0;
        if ((n - k) % 2 == 0) {
            int val = (n - k) / 2;
            odds = nCr(val + k - 1, k - 1);
        }
        
        return (total - odds + MOD) % MOD;
    }
}

#Python
class Solution:
    def __init__(self):
        self.MOD = 10**9 + 7
        self.fact = []
        self.inv_fact = []

    def calculateFactorial(self, n: int):
        self.fact[0] = 1
        for i in range(1, n + 1):
            self.fact[i] = (i * self.fact[i - 1]) % self.MOD

    def moduloBinaryExponentiation(self, a: int, b: int) -> int:
        res = 1
        while b > 0:
            if b & 1:
                res = (res * a) % self.MOD
            a = (a * a) % self.MOD
            b >>= 1
        return res

    def calculateInverseFactorial(self, n: int):
        self.inv_fact[0] = 1
        # Loop backwards from n-1 down to 1
        for i in range(n - 1, 0, -1):
            self.inv_fact[i] = ((i + 1) * self.inv_fact[i + 1]) % self.MOD

    def nCr(self, n: int, r: int) -> int:
        if r < 0 or r > n:
            return 0
        # Python handles large numbers automatically, no 1LL needed
        return (self.fact[n] * self.inv_fact[r] * self.inv_fact[n - r]) % self.MOD

    def countValidSequences(self, n: int, k: int) -> int:
        # Step-1: Precompute Factorial & Inverse Factorial
        self.fact = [0] * (n + 1)
        self.inv_fact = [0] * (n + 1)
        
        self.calculateFactorial(n)
        self.inv_fact[n] = self.moduloBinaryExponentiation(self.fact[n], self.MOD - 2)
        self.calculateInverseFactorial(n)

        # Step-2: Total +ve Sequence count (Odd + Even) = C(n-1,k-1)
        total = self.nCr(n - 1, k - 1)

        # Step-3: Count total odd sequences = C(((n-k)/2 + k - 1), k-1)
        odds = 0
        if (n - k) % 2 == 0:
            val = (n - k) // 2
            odds = self.nCr(val + k - 1, k - 1)
            
        return (total - odds + self.MOD) % self.MOD
*/