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 int N = 2e6 + 10;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
const LL mod=1e9+7;
int k;
char a[N];
LL dp[111][111];
LL pm(LL x,LL y){
	if(!x)return 1;
	LL z=1;
	while(y){
		if(y&1)z=z*x%mod;
		y>>=1;
		x=x*x%mod;
	}
	return z;
}
LL fac[N],inv[N];
void P(){
	fac[0]=1;
	for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%mod;
	inv[N-1]=pm(fac[N-1],mod-2);
	for(int i=N-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
}
LL get(int x,int y){
	//cout<<x<<' '<<y<<' '<<fac[x]*inv[y]%mod*inv[x-y]<<endl;
	return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int main() {
  ios::sync_with_stdio(false);
  cin>>k>>a+1;P();
  int n=strlen(a+1);
  LL ans=0;
  for(int i=0;i<=k;i++){
  	int last=k-i;
  	ans+=pm(26,i)*pm(25,last)%mod*get(last+n-1,n-1)%mod;
  	ans%=mod;
  }
  cout<<ans<<'\n';
 	return 0;
}