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;
#define mod 1000000007
using ll=long long;
ll factorial[2000010];

ll power(ll n,ll m)
{
    ll ans=1;
    for (ll r=0;m>>r>0;r++)
    {
        if ((m>>r)&1) ans=ans*n%mod;
        n=n*n%mod;
    }
    return ans;
}

ll inv(ll n)
{
    return power(n,mod-2);
}

void fact()
{
    factorial[0]=1;
    for (ll i=1;i<2000010;i++) factorial[i]=i*factorial[i-1]%mod;
    return;
}

ll cmb(ll n,ll r)
{
    if (r>n) return 0;
    else return factorial[n]*inv(factorial[n-r])%mod*inv(factorial[r])%mod;
}

int main()
{
    fact();
    ll k;cin >> k;
    string S;cin>> S;
    ll si=S.size();
    ll ans=0;
    for (ll i=si;i<si+k+1;i++)
    {
        ans=(ans+power(25,i-si)*cmb(i-1,si-1)%mod*power(26,si+k-i)%mod)%mod;
    }
    cout << ans%mod << endl;
    return 0;
}