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;
ll read(){
	ll a=0,b=getchar(),c=1;
	while(!isdigit(b))c=b=='-'?-1:1,b=getchar();
	while(isdigit(b))a=a*10+b-'0',b=getchar();
	return a*c;
}
ll n,k,j,mod=1e9+7,a[2000005]={1};
string s;
ll jj(ll x,ll y){
	ll res=1;
	while(y){
		if(y%2)res=(res*x)%mod;
		x=x*x%mod,y/=2;
	}
	return res;
}
ll gg(ll n,ll r){
	ll n1=a[n],n2=a[n-r],n3=a[r];
	n2=n2*n3%mod;
	n3=jj(n2,mod-2);
	n1=n1*n3%mod;
	return n1;
}
int main(){
	for(int i=1;i<2e6+5;i++)
		a[i]=i*a[i-1]%mod;
	k=read();
	cin >> s;
	n=s.size(),j=jj(26,k+n);
	ll xx=n+k,j1=0;
	for(int i=0;i<n;i++){
		ll x=gg(xx,i),y=jj(25,xx-i);
		x*=y,x%=mod;
		j1+=x,j1%=mod;
	}
	j=(j-j1+mod)%mod;
	cout << j;
	return 0;
}