牛客竞赛题目讲解_Counting regions

// https://ac.nowcoder.com/acm/contest/33549/G

#include<bits/stdc++.h>

typedef long long LL;

const LL mod = 1e9+7;

LL Pow(LL a,LL n)

{

    LL ans = 1;

    while(n)

    {

        if(n&1) ans = ans * a % mod;

        a = a*a % mod;

        n >>= 1;

    }

    return ans;

}

LL Inv(LL n)

{

    return Pow(n,mod-2);

}

int main()

{

    LL n;

    std::cin>>n;

    // C(n,2)%mod + C(n,4)%mod -n +1 %mod

    LL E = (n-1)/2*n%mod;

    LL V = n*(n-1)%mod*(n-2)%mod*(n-3)%mod*Inv(24)%mod;

    LL ans = E+V-n+1+mod;

    std::cout<<ans%mod<<std::endl;

    return 0;

}