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;
ll mod = 1000000007;
ll pow_mod(ll a, ll b) {
    if (b == 0) {
        return 1;
    }
    ll c = pow_mod(a, b/2);
    c = (c*c) % mod;
    if (b % 2 == 0) return c;
    return (c*a) % mod;
}
ll x[2000001] = {1};
ll nCk(ll n, ll k) {
    ll X = x[n], Y = (x[k]*x[n-k]) % mod;
    return (X*pow_mod(Y, mod-2)) % mod;
}
int main() {
    for (int i = 1; i <= 2000000; i++) {
        x[i] = x[i-1] * i;
        x[i] %= mod;
    }
    ll K;
    string S;
    cin >> K >> S;
    int a = S.size();
    int z = 26;
    ll ans = pow_mod(z, a+K);
    ll e = 1;
    for (int i = 1; i <= K+1; i++)  {
        e *= z-1;
        e %= mod;
    }
    for (int i = a-1; i >= 0; i--) {
        ans -= (nCk(a+K, i)*e);
        ans %= mod;
        e = (e*(z-1)) % mod;
    }
    ans += mod+mod;
    ans %= mod;
    cout << ans << endl;
}