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;
typedef long long ll;
const ll Max=2e6+10, N=2e6+100, mod=1e9+7;

ll fct[N],k,ans,n;
string s;

ll qmi(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1) res=res*a%mod;
		b>>=1; a=a*a%mod;
	}
	return res;
}
ll C(ll a,ll b){
	if(a<b) return 0;
	return fct[a]*qmi(fct[b],mod-2)%mod*qmi(fct[a-b],mod-2)%mod;
}
void init(){
	fct[0]=1;
	for(ll i=1;i<=Max;i++) fct[i]=fct[i-1]*i%mod;
}


int main(){
	cin>>k;
	cin>>s;
	init();
// wa	
	ll len=s.size();
	n=len+k;
	ans=0;
	for(ll i=len;i<=n;i++){
		//C(i-1,len-1);
		//qmi(25,i-len);
		//qmi(26,n-i)%mod;
		//ans+C(i-1,len-1)*qmi(25,i-len)%mod;
		//ans+C(i-1,len-1)*qmi(25,i-len)%mod*qmi(26,n-i)%mod;
		//ll t=(C(i-1,len-1)*qmi(25,i-len)%mod*qmi(26,n-i)%mod)%mod;
		//ans = ((ans+t)%mod+mod)%mod;
		ans=(ans+C(i-1,len-1)*qmi(25,i-len)%mod*qmi(26,n-i)%mod)%mod;
	}
	cout<<ans<<endl;
	return 0;
} 