Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define ull long long
- #define MOD 1000000007
- using namespace std;
- ull inverseMult(ull a, ull b, ull s0 = 1, ull s1 = 0) {
- return (b == 0) ? s0 : inverseMult(b, a % b, s1, s0 - (s1*(a/b)));
- }
- ull binomialCoeff(ull n, ull k) {
- ull res = 1;
- k = (k > n - k) ? n - k : k;
- for(ull i = 0; i < k; i++) {
- res = ((res%MOD) * ((n-i)%MOD)) % MOD;
- res += (res < 0) ? MOD : 0;
- ull temp = inverseMult(i + 1, MOD);
- temp += (temp < 0) ? MOD : 0;
- res = (res % MOD * temp % MOD) % MOD;
- }
- return res;
- }
- ull solve(ull n) {
- ull c = binomialCoeff(2 * n, n) - binomialCoeff(2 * n, n + 1);
- ull temp = inverseMult(n + 1, MOD);
- temp += (temp < 0) ? MOD : 0;
- return ((c % MOD) * (temp % MOD)) % MOD;
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- ull n;
- cin >> n;
- cout << solve(n) % MOD;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement