nCr v2

/*
Sử dụng công thức truy hồi:
    nCr = (n-1)Cr + (n-1)C(r-1)

ta dễ dàng khởi tạo tất cả các giá trị nCr trong O(N^2).

Code có thể chạy được với n <= 5000 và mod bất kỳ (không cần nguyên tố).
*/
//by Tanmay Chaudhari
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
long long ncr[5005][5005];

void precompute()
{
    int k;
    for (int i = 0; i < 5001; i++)
    {
        ncr[i][0] = ncr[i][i] = 1;
        k = i >> 1;
        for (int j = 1; j < k + 1; j++)
            ncr[i][j] = ncr[i][i - j] = (ncr[i - 1][j] + ncr[i - 1][j - 1]) % MOD;
    }
}

int main()
{
    precompute();
    cout << ncr[4892][231] << endl;
    return 0;
}