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;
typedef long long ll;

const int M = 1e9 + 7;

ll qpow(ll x, ll p) {
    ll res = 1;
    while (p) {
        if (p & 1) res = res * x % M;
        p >>= 1;
        x = x * x % M;
    }
    return res;
}

ll divide(ll x, ll y) {
    return x * qpow(y, M - 2) % M;
}

int main() {
    int k;
    string s;
    cin >> k >> s;
    vector<ll> pw25(k + 1), pw26(k + 1);
    pw25[0] = 1, pw26[0] = 1;
    for (int i = 1; i <= k; i++) {
        pw25[i] = pw25[i - 1] * 25 % M;
        pw26[i] = pw26[i - 1] * 26 % M;
    }
    int l = s.size(), n = l + k;
    ll comb = 1, ans = 0;
    for (int i = l - 1; i < n; i++) {
        ans = (ans + (comb * pw25[i + 1 - l] % M) * pw26[n - i - 1]) % M;
        comb = comb * divide(i + 1, i + 2 - l) % M;
    }
    cout << ans << "\n";
}
