题解 | Y型树

// // 活动地址： 牛客春招刷题训练营 - 编程打卡活动


// #include <ios>
// #pragma clang diagnostic push

// #pragma ide diagnostic ignored "cppcoreguidelines-narrowing-conversions"

// #pragma ide diagnostic ignored "hicpp-signed-bitwise"

// #pragma GCC optimize ("Ofast,unroll-loops")

// #pragma GCC optimize("no-stack-protector,fast-math")

 

// #include <bits/stdc++.h>

// using namespace std;

// typedef long long ll;

// typedef pair<ll, ll> pll;

// typedef pair<int, int> pii;

// typedef pair<double, double> pdd;   

// typedef vector<int> vi;

// typedef vector<ll> vll;

// typedef vector<double> vd;

// typedef vector<string> vs;

// typedef vector<vi> vvi;

// typedef vector<vvi> vvvi;

// typedef vector<vll> vvll;

// typedef vector<vvll> vvvll;

// typedef vector<pii> vpii;

// typedef vector<vpii> vvpii;

// typedef vector<pll> vpll;

// typedef vector<vpll> vvpll;

// typedef vector<pdd> vpdd;

// typedef vector<vd> vvd;

// #define yn(ans) printf("%s\n", (ans)?"Yes":"No");

// #define YN(ans) printf("%s\n", (ans)?"YES":"NO");

// template<class T> bool chmax(T &a, T b) {

//     if (a >= b) return false;

//     a = b; return true;

// }

// template<class T> bool chmin(T &a, T b) {

//     if (a <= b) return false;

//     a = b; return true;

// }

// #define FOR(i, s, e, t) for ((i) = (s); (i) < (e); (i) += (t)) 

// #define REP(i, e) for (int i = 0; i < (e); ++i) 

// #define REP1(i, s, e) for (int i = (s); i < (e); ++i)

// #define RREP(i, e) for (int i = (e); i >= 0; --i)

// #define RREP1(i, e, s) for (int i = (e); i >= (s); --i)

// #define all(v) v.begin(), v.end()

// #define pb push_back

// #define qb pop_back

// #define pf push_front

// #define qf pop_front

// #define maxe max_element

// #define mine min_element

// ll inf = 1e18;

// #define DEBUG printf("%d\n", __LINE__); fflush(stdout);

// template<class T> void print(vector<T> &v, bool withSize = false) {

//     if (withSize) cout << v.size() << endl;

//     REP(i, v.size()) cout << v[i] << " "; 

//     cout << endl;

// }

// mt19937_64 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());

 

// int __FAST_IO__ = []() {

//     std::ios::sync_with_stdio(0);

//     std::cin.tie(0);

//     std::cout.tie(0);

//     return 0;

// }();

// #include<bits/stdc++.h>

// using  namespace std;

// #define mod 1000000007

// typedef long long ll;

// #define int  long long

// inline ll read() // void int &n

// {

//     ll s=0,f=1;

//     char c=getchar();

//     while(c>'9'||c<'0')     

// {

//         if(c=='-')  

//             f=-1;   

//         c=getchar();

//     }

//     while(c>='0'&&c<='9')

//     {

//         s=(s<<1)+(s<<3)+c-'0';

//         c=getchar();

//     }

//     return s*f;

// }

// inline void write(int n)

// {

// if(n<0)

// {

//   putchar('-');

//   n=-n;

// }

    

// if(n>10) write(n/10);

// putchar(n%10+'0');

// }

// int jiechen(int n)

// {

//     int sum = 1;

//     for (int i = 2; i <= n; i++)

//         sum = sum * i % mod;

//     return sum % mod;

// }

// int qsm(ll a, ll p)

// {

//     ll s=1;

//     while(p)

//     {

//         if(p&1)

//          s=s*a%mod;

//       a=a*a%mod;

//     }

//        return s;

// }

// ll isprime(ll x)

// {

//     if(x<2)

//         return 0;

//     for(int i=2;i<=x/i;i++)

//         if(x%i==0)

//             return 0;

//     return 1;

// }

// const int N=3e6+10;


// void solve(){
 
// }

// signed main()

// {

// ios::sync_with_stdio(false);

// cin.tie(0);

// cout.tie(0);

//     int _=1;

//    // cin>>_;

//     while(_--)

//     {

//         solve();

//     }

//     return 0;

// }
 // 好久没做题了看不懂思密达 555
// // 活动地址： 牛客春招刷题训练营 - 编程打卡活动
#include <iostream>
using namespace std;
using ll = long long;
const int mod = 1000000007;

ll modpow(ll a, ll b) {
    ll res = 1 % mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

ll sum(ll x) {
    x %= mod;
    return x % mod * (x + 1) % mod * modpow(2, mod-2) % mod;
}

ll calc(ll x) {
    ll ret = sum(x/2) * 2 % mod;
    if(x % 2 == 0) ret += mod - x/2 % mod, ret %= mod;
    return ret;
}

int main() {
    ll n;
    cin >> n;
    n--;  // 除去分叉点
    ll k = n/3;  // 最大组的点数
    ll ans = 0;
    ans += calc(n-1) + mod - calc(n-k-1), ans %= mod;
    ans += mod - sum(k) % mod, ans %= mod;
    ans += k, ans %= mod;
    cout << ans << endl;
    return 0;
}