HackerRank - longest increasing subsequence - study code - C# world code sprint #5

longestIncreasingSubsequence1.cs

using System;
using System.Linq;
using System.Collections.Generic;
class Solution
{
    static long Modulus = 1000L * 1000L * 1000L + 7L;
    static void Main(string[] args)
    {
        int p = int.Parse(Console.ReadLine());
        BinomialCoefficients bc = new BinomialCoefficients(5 * 100 * 1000, Modulus);
        for (int i = 0; i < p; i++)
        {
            int[] mn = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            Console.WriteLine(Solve(mn[0], mn[1],bc));
        }


    }
    static long Solve(int m, int n, BinomialCoefficients bc)
    {
        if (m < n)
            return 0;
        long s = 0;
        long[] nPows = new long[m - n + 1];
        long[] nMinusOnePows = new long[m - n + 1];
        nPows[0] = 1;
        nMinusOnePows[0] = 1;
        for (int i = 1; i < m - n + 1; i++)
        {
            nPows[i] = (nPows[i - 1] * n)%Modulus;
            nMinusOnePows[i] = (nMinusOnePows[i - 1] * (n - 1))%Modulus;
        }
        for (int i = 0; i <= m - n; i++)
        {
            s += ((nPows[i] * nMinusOnePows[m-n-i]) % Modulus) * bc.NItemsMBuckets(m - i - n, n);
            s %= Modulus;
        }
        return s;
    }
}

class BinomialCoefficients
{
    long[] Factorial;
    long[] FactorialInverse;
    long PrimeModulus;
    public long this[int n, int k]
    {
        get
        {
            long u = Factorial[n] * FactorialInverse[n - k];
            u %= PrimeModulus;
            u = u * FactorialInverse[k];
            u %= PrimeModulus;
            return u;
        }
    }
    public BinomialCoefficients(int maxIndex, long primeModulus)
    {
        PrimeModulus = primeModulus;
        CacheFactorials(maxIndex);
    }
    void CacheFactorials(int nmax)
    {
        Factorial = new long[nmax + 1];
        FactorialInverse = new long[nmax + 1];
        Factorial[0] = 1;
        for (int i = 1; i < Factorial.Length; i++)
            Factorial[i] = (Factorial[i - 1] * i) % PrimeModulus;
        for (int i = 0; i < Factorial.Length; i++)
            FactorialInverse[i] = GetInverse(Factorial[i]);

    }
    long GetInverse(long n)
    {
        return GetPower(n, PrimeModulus - 2);
    }
    long GetPower(long bas, long power)
    {
        long s = 1;
        while (power > 0)
        {
            if (power % 2 == 1)
                s = (s * bas) % PrimeModulus;
            bas = (bas * bas) % PrimeModulus;
            power /= 2;
        }
        return s;

    }
    public long NItemsMBuckets(int n, int m)
    {
        return this[n + m - 1, m - 1];
    }
}