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
#include <bits/stdc++.h>
using namespace std;

// find the modular inverse using extended Euclidean algorithm
long long modinv(long long a, long long mod) {
    long long b = mod, u = 1, v = 0;
    while (b) {
        long long q = a / b;
        a -= q * b;
        swap(a, b);
        u -= q * v;
        swap(u, v);
    }
    u %= mod;
    if (u < 0) {
        u += mod;
    }
    return u;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int K;
    cin >> K;
    string S;
    cin >> S;
    long long mod = 1E9 + 7;
    int L = S.length();
    long long cur = 1;
    long long C = 1;
    for (int i = 0; i < K; ++i) {
        C = (((C * (L + i)) % mod) * modinv(i + 1, mod) % mod) * 25 % mod;
        cur = (cur * 26 + C) % mod;
    }
    cout << cur << '\n';
    return 0;
}