Submission #65074728

---

Source Code Expand

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

using ll = long long;
using mint = modint1000000007;

int main(){
    int K; cin >> K;
    string S; cin >> S;

    int mod = 1000000007;
    int N = S.size(), M = N + K + 10;
    vector<mint> fact(M), inv(M), rfact(M);
    inv[0] = inv[1] = 1;
    for(int i = 2; i < M; ++i){
        inv[i] = -inv[mod % i] * (mod / i);
    }
    fact[0] = rfact[0] = fact[1] = rfact[1] = 1;
    for(int i = 2; i < M; ++i){
        fact[i] = fact[i - 1] * i;
        rfact[i] = rfact[i - 1] * inv[i];
    }
    auto Combination = [&](int n, int r) -> mint {
        if(r < 0 or r > n) return 0;
        return fact[n] * rfact[r] * rfact[n - r];
    };
    auto Homogeneous = [&](int n, int r) -> mint {
        if(n < 0 or r < 0) return 0;
        return r == 0 ? 1 : Combination(n + r - 1, r);
    };

    mint ans = 0, x = mint(25).pow(K), y = 1;
    for(int i = 0; i <= K; ++i, x /= 25, y *= 26){
        ans += Homogeneous(N, K - i) * x * y;
    }
    cout << ans.val() << endl;
}

Submission Info

Judge Result