Advertisement
Alexvans

Untitled

Jun 16th, 2017
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.69 KB | None | 0 0
  1. #include <iostream>
  2. #define ull unsigned long long
  3. using namespace std;
  4.  
  5. ull OMI(ull a, ull b, ull s0 = 1, ull s1 = 0) {
  6.     return b==0? s0: OMI(b, a%b, s1, s0 - s1*(a/b));
  7. }
  8.  
  9. ull binomialCoeff(ull n, ull k) {
  10.     ull res = 1;
  11.     if (k > n - k)
  12.         k = n - k;
  13.     for (ull i = 0; i < k; ++i) {
  14.         res *= (n - i);
  15.         res /= (i + 1);
  16.     }
  17.     return res;
  18. }
  19.  
  20. ull catalan(ull n) {
  21.     ull c = binomialCoeff(2*n, n);
  22.     ull temp = OMI(n + 1, 1000000007);
  23.     return (c * ((temp < 0) ? (temp + 1000000007) : temp))%1000000007;
  24. }
  25.  
  26. int main() {
  27.     ull n;
  28.     cin >> n;
  29.     if(n == 1) {
  30.         cout << 1;
  31.         return 0;
  32.     }
  33.     cout << catalan(n) % 1000000007;
  34. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement