Jubilee

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
#define til(n) for(ll i = 0; i < n; i++)

constexpr ll mod = 1e9+7;


ll euclid(ll a, ll b, ll& x, ll& y){
    if (!b) return x=1,y=0,a;
    ll d = euclid(b,a%b,y,x);
    return y-=a/b * x, d;
}

struct Mod {
    ll x;
    Mod(ll xx) : x(xx) {}
    Mod operator* (Mod b) { return Mod((x * b.x) % mod); }
    Mod operator/ (Mod b) { return *this * invert(b); }
    Mod operator- (Mod b) { return Mod((x-b.x+mod) % mod); }
    Mod operator+ (Mod b) { return Mod((x+b.x) % mod); }
    Mod invert(Mod a) {
        ll x,y,g = euclid(a.x,mod,x,y);
        assert (g==1);
        return Mod((x+mod) % mod);
    }
};


int main() {
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0)->sync_with_stdio(false);
    ll n2, m2;
    cin >> n2 >> m2;
    Mod n(n2);
    Mod m(m2);
    Mod total = 1;
    // first two seats at the end of the table
    total = total * m;
    total = total * (m - 1);
    til(n2-1) {
        auto same = total;
        auto diff = total * (m - 2);
        total = (same * (m-1)) + (diff * (m-2));
    }
    cout << total.x << '\n';
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED