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 LL long long
#define FAST() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

LL fact[2000002];
const LL mod=1e9+7;

LL BigMod(LL val,LL pow)
{
    LL res = 1;
    val = val % mod;
    while(pow > 0)
    {
        if(pow & 1)res = (res*val) % mod;
        pow = pow >> 1;
        val = (val*val) % mod;
    }
    return res;
}

LL nCr(LL n,LL r)
{
    if(n < r)return 0;
    return fact[n]*BigMod(fact[r]*fact[n-r],mod-2)%mod;
}

int main()
{
    FAST();
    string s;
    fact[0]=1;
    LL i,k,l,ans=0;
    cin >> k >> s;
    l=(LL)s.size();
    for(i=1;i<=k+l;i++)fact[i]=(fact[i-1]*i)%mod;
    for(i=0;i<=k;i++)
    {
        ans+=nCr(k+l-i-1,l-1)*(BigMod(26,i)*BigMod(25,k-i)%mod)%mod;
        if(ans >= mod)ans-=mod;
    }
    cout << ans;
    return 0;
}
