How many strings can be obtained by applying the following operation on a string S exactly K times: "choose one lowercase English letter and insert it somewhere"?

The answer can be enormous, so print it modulo (10^9+7).

Constraints

* K is an integer between 1 and 10^6 (inclusive).
* S is a string of length between 1 and 10^6 (inclusive) consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:


K
S


Output

Print the number of strings satisfying the condition, modulo (10^9+7).

Examples

Input

5
oof


Output

575111451


Input

37564
whydidyoudesertme


Output

318008117
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

const ull MOD = 1000000007;

ull modpow(ull a, ull n, ull mod) {
    ull res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

ull modinv(ull a, ull mod) {
    return modpow(a, mod - 2, mod);
}

int main() {
    ull K;
    string s;
    cin >> K >> s;
    ull ans = 1;
    ull pow_25 = 1;
    ull comb = 1;
    vector<ull> inv(K+s.size());
    for (ull i = 0; i < inv.size(); i++) {
        inv[i] = modinv(i+1, MOD);
    }
    for (ull i = 0; i < K; i++) {
        pow_25 = (pow_25 * 25) % MOD;
        comb = (((comb * (s.size()+i)) % MOD) *inv[i]) % MOD;
        ans = ((ans * 26) % MOD + (pow_25 * comb) % MOD) % MOD;
    }
    cout << ans << endl;
    return 0;
}
