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 mod=1e9+7; 
const int SIZE=1<<21;
string s;
int k;
ll fac[SIZE],rev[SIZE];
inline ll Pow(ll x,ll y){
	ll res=1;
	while(y){
		if(y&1){
			res=res*x%mod;
		}
		y>>=1;
		x=x*x%mod;
	}
	return res;
}
inline ll C(int x,int y){
	if(y<0||y>x){
		return 0;
	}
	return fac[x]*rev[y]%mod*rev[x-y]%mod;
} 
inline void build(){
	fac[0]=1;
	for(int i=1;i<SIZE;++i){
		fac[i]=fac[i-1]*i%mod;
	}
	rev[SIZE-1]=Pow(fac[SIZE-1],mod-2);
	for(int i=SIZE-2;i>=0;--i){
		rev[i]=rev[i+1]*(i+1)%mod;
	}
}
int main(){
	cin>>k>>s;
	build();
	int n=s.size();
	long long ans=0;
	for(int i=n;i<=k+n;++i){
		ans+=C(k+n,i)*Pow(25,k+n-i)%mod;
		ans%=mod;
	}
	cout<<ans<<'\n';
	return 0;
}
