C++ 解法, 执行用时: 1246ms, 内存消耗: 78592K, 提交时间: 2021-06-20 09:49:41

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int mod = 421969921;
const int maxn = 10000100;

int fac[maxn], ifac[maxn];

int qpow(int a, int n) {
    int ans = 1; for ( ; n; n>>=1, a=(ll)a*a%mod) if (n&1) ans=(ll)ans*a%mod;
    return ans;
}

int main(void) {
    int n; ll m; scanf("%d%lld", &n, &m);
    m %= (mod - 1);

    fac[0] = 1; for (int i=1; i<=n; i++) fac[i] = fac[i-1] * (ll)i % mod;
    ifac[n] = qpow(fac[n], mod - 2);
    for (int i=n-1; i>=0; i--) ifac[i] = ifac[i+1] * (ll)(i+1) % mod;

    int f = 1, ans = qpow(n, m);
    for (int i=n-1; i>=1; i--) {
        ans = (ans + qpow(i, m + 1) * (ll)f % mod * ifac[n - i]) % mod;
        f = f * (ll)n % mod;
    }
    ans = (ll)ans * fac[n] % mod;
    printf("%d\n", ans);
    return 0;
}