ABC 307

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, M;
    cin >> N >> M;

    // dp[i][f]: i 番目の数が 0 番目の数と同じ(f=1)/違う(f=0)ときの場合の数
    vector dp(N, vector<mint>(2));
    dp[0][1] = M;
    rep2(i, 1, N) {
        // i 番目は 0 番目と同じ数字になる、かつ、同じ数字が連続してはいけないので i-1 番目の数は 0 番目の数とは違う
        dp[i][1] += dp[i - 1][0];

        // i 番目が 0 番目と異なる数字のとき、i-1 番目の数は 0 番目と同じか異なるのどちらでもいける。
        // i-1 番目の数が 0 番目と同じ時、i 番目の数は 0 番目とは違う M-1 通りが考えられる
        // i-1 番目の数が 0 番目と異なる時、i 番目の数は 0 番目とは異なり i-1 番目の数とも異なるから M-2 通りが考えられる
        dp[i][0] += dp[i - 1][1] * (M - 1) + dp[i - 1][0] * (M - 2);
    }
    cout << dp[N - 1][0].val() << endl;
}