Advertisement
Alexvans

Untitled

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