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;
using ll = long long;

const int mod = 1e9 + 7;
const int MX  = 2e6;

ll power(ll x, ll y, ll p = mod) {
    ll res = 1;
    x      = x % p;
    while (y) {
        if (y & 1) res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}

ll modInverse(ll n, ll p = mod) { return power(n, p - 2, p); }

ll fac[MX + 5];
void init(ll p = mod) {
    fac[0] = 1;
    for (int i = 1; i <= MX; i++) fac[i] = fac[i - 1] * i % p;
}

ll C(ll n, ll r, ll p = mod) {
    if (r == 0) return 1;
    if (n - r < r) return C(n, n - r, p);
    return fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p;
}

int main() {
    init(mod);
    int n, k;
    string s;
    cin >> k >> s;
    n    = s.size() + k;
    ll r = 0;
    for (int i = s.size(); i <= n; ++i)
        (r += C(n, i) * power(25, n - i)) %= mod;
    cout << r;
}