NCK O(N)

int nck(int N, int K) {
  if (K < N - K)
    K = N - K;
  int ans = 1, p = 2;
  for (int i = K + 1; i <= N; ++i) {
    ans *= i;
    while (p <= N - K && ans % p ==0)
      ans /= p++;
  }
  return ans;
}