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 <iostream>
#include <vector>

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;

vector<ll> sil(3000000);

ll Pot(ll p, ll w)
{
    if (w == 0)
        return 1;
    if (w % 2 == 0)
    {
        ll pol = Pot(p, w / 2);
        return pol * pol % MOD;
    }
    return Pot(p, w - 1) * p % MOD;
}

ll Inv(ll x)
{
    return Pot(x, MOD - 2);
}

ll C(ll n, ll k)
{
    return sil[n] * (Inv(sil[k]) * Inv(sil[n - k]) % MOD) % MOD;
}

int main()
{
    ios_base::sync_with_stdio(0);
    sil[0] = 1;
    for (ll i = 1; i < 3000000; ++i)
        sil[i] = (sil[i - 1] * i) % MOD;
    ll k;
    string s;
    cin >> k >> s;
    ll n = s.size();
    ll odp = 0;
    for (ll i = n; i <= n + k; ++i)
    {
        ll il = (C(i - 1, n - 1) * Pot(25, i - n)) % MOD;
        il = (il * Pot(26, n + k - i)) % MOD;
        odp = (odp + il) % MOD;
    }
    cout << odp;
    return 0;
}
