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>
#define ll long long

using namespace std;

const ll mod = 1e9 + 7;
ll k, fact[2000005], ans;
string s;

ll find(ll x) {
    if (x == 1) return x;
    return (mod - mod / x) * find(mod % x) % mod;
}

ll comb(ll x, ll y) {
    return (fact[y] * find(fact[y - x]) % mod * find(fact[x])) % mod;
}

int main() {
    cin >> k >> s;
    fact[0] = 1;
    for (ll i = 1; i <= 2000000; i++) {
        fact[i] = fact[i - 1] * i % mod;
    }
    ll pow = 1;
    for (ll i = 1; i <= k; i++) pow = pow * 25 % mod;
    for (ll i = 0; i <= k; i++) {
        ans = (ans + pow * comb(s.length() - 1, k - i + s.length() - 1)) % mod;
        pow = (pow * find(25) * 26) % mod;
    }
    if (ans < 0) ans += mod;
    cout << ans << endl;
    return 0;
}