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>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<map>
#include<set>
#include<cstdlib>
#include<bitset> 
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll qpow(ll a,ll b)
{
	if(b==0) return 1;
	ll c=qpow(a,b/2);
	if(b%2==0) return c*c%mod;
	else return c*c%mod*a%mod;
} 
ll fac[2000006]={0};
char s[2000006];
ll cnm(ll n,ll m)
{
	return fac[n]*qpow(fac[n-m],mod-2)%mod*qpow(fac[m],mod-2)%mod;
}
int main(void)
{
	fac[0]=1;
	for(ll i=1;i<=2000000;i++)
	{
		fac[i]=fac[i-1]*i%mod;
	}
	ll ans=0;
	ll n,k;
	scanf("%lld %s",&k,s);
	n=strlen(s);
	for(ll i=0;i<=k;i++)
	{
		ans+=cnm(n+i-1,n-1)*qpow(25,i)%mod*qpow(26,k-i)%mod;
	}
	printf("%lld\n",ans%mod);
}