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>
using namespace std;
const int maxn=2e6+10;
const int mod=1e9+7;
long long fac[maxn], inv[maxn];
long long qp(long long a, long long b) {
    long long res=1;
    while (b)
	{
        if (b&1)
			res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
long long C(long long n, long long m)
{
   	return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main()
{
	int k,i,j;
	string s;
    fac[0]=1;
    for(i=1;i<maxn;i++)
        fac[i]=fac[i-1]*i%mod;
    inv[maxn-1]=qp(fac[maxn-1],mod-2);
    for(i=maxn-2;i>=0;i--)
        inv[i]=inv[i+1]*(i+1)%mod;
	cin>>k>>s;
    int n=k+s.size();
    long long ans=0;
    for (int i=s.size();i<=n;i++)
        ans+=C(n,i)*qp(25,n-i)%mod,ans%=mod;
    cout<<ans<<endl;
}