Submission #995061

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
 
const long long MOD = 1000000007;
const int INF = 1<<29;
const double EPS = 1e-8;
typedef vector<int> vec;
typedef pair<int,int> P;
typedef long long ll;


int main(){
    ll N, M;
    cin >> N >> M;

    // n_1[k] = (N - 1)^k, n_2[k] = (N - 2) ^ k
    vector<ll> n_1(M), n_2(M);
    n_1[0] = 1;
    n_2[0] = 1;
    for(ll i=1;i<M;i++){
        n_1[i] = (n_1[i-1] * (N - 1)) % MOD;
        n_2[i] = (n_2[i-1] * (N - 2)) % MOD;
    }

    // np[k] = n^k
    vector<ll> np(M+1);
    np[0] = 1;
    for(int i=1;i<=M;i++){
        np[i] = (np[i-1] * N) % MOD;
    }

    ll ans = 0;
    for(ll k=N-1;k<=M-1;k++){
        ll left = ((N - 1) * (n_1[k - 1] - n_2[k] + MOD) % MOD);
        ll right = np[M - k - 1];
        ans = (ans + left * right) % MOD;
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result