Advertisement
marius7122

Untitled

Jun 5th, 2021
899
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.62 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. #define ll long long
  4.  
  5. using namespace std;
  6.  
  7. const int MOD = 1e9 + 7;
  8.  
  9. ll fact(ll x)
  10. {
  11.     ll f = 1;
  12.     for(int i = 2; i <= x; i++)
  13.         f = (f * i) % MOD;
  14.     return f;
  15. }
  16.  
  17. ll fastExp(ll x, ll p)
  18. {
  19.     ll ans = 1;
  20.     ll currPow = x;
  21.     for(int bit = 0; bit < 30; bit++)
  22.     {
  23.         if((1 << bit) & p)
  24.             ans = (ans * currPow) % MOD;
  25.         currPow = (currPow * currPow) % MOD;
  26.     }
  27.     return ans;
  28. }
  29.  
  30. ll inv(ll x)
  31. {
  32.     return fastExp(x, MOD - 2);
  33. }
  34.  
  35. int main()
  36. {
  37.     ll n, c;
  38.     cin >> n;
  39.  
  40.     c = fact(2*n) * inv((fact(n) * fact(n+1)) % MOD);
  41.     cout << c % MOD << '\n';
  42.     return 0;
  43. }
  44.  
  45.  
  46.  
  47. // n => (2n)! / (n+1)!*n!
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement