题目3 : 树的方差

#include<cstdio>

#include<iostream>

using namespace std;

typedef long long ll;

const ll mod=;

ll fpow(ll a,ll p){

    ll res=;

    for(;p;p>>=,a=a*a%mod) if(p&) res=res*a%mod;

    return res;

}

ll n,tem,ans;

int main(){

    cin>>n;

    ans=(n-)*(n-)%mod;

    if(n<=){

        tem=fpow(n,mod-);

        ans=ans*tem%mod;

        cout<<ans<<'\n';

        return ;

    }

    tem=fpow(n,n-);

    ans=ans*tem%mod;

    cout<<ans<<'\n';

    return ;

}