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;
const int N=2e6+5,mo=1e9+7;
typedef long long LL;
char s[N];
void Inverse(int p,int a[],int n){//ÏßÐÔÇó<=nµÄÊý%pÒâÒåÏÂµÄÄæÔª 
	a[1]=1;
	for(int i=2;i<=n;i++){
		a[i]=1ll*(p-p/i)*a[p%i]%p;
	}
}
int inv[N],fac[N],pow25[N],pow26[N];
void init(int n){
	pow25[0]=pow26[0]=fac[0]=inv[0]=1;Inverse(mo,inv,n);
	for(int i=1;i<=n;i++)inv[i]=1ll*inv[i-1]*inv[i]%mo,fac[i]=1ll*i*fac[i-1]%mo,pow25[i]=25ll*pow25[i-1]%mo,pow26[i]=26ll*pow26[i-1]%mo;
}
int C(int n,int m){return 1ll*fac[n]*inv[m]%mo*inv[n-m]%mo;}
int main(){
	int k,l;scanf("%d%s",&k,s),l=strlen(s);
	LL ans=0;
	init(k+l);
	for(int i=0;i<=k;i++){
		(ans+=1ll*pow26[k-i]*pow25[i]%mo*C(l+i-1,i)%mo)%=mo;
	}
	printf("%d",ans);
	return 0;
}