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;
#define ll long long
const ll mod=1e9+7;
ll fp(ll b, ll e){
	ll rs=1ll;
	for(;e>0;e/=2, b=(b*b)%mod)
		if(e%2==1) rs=(rs*b)%mod;
	return rs;
}
ll fc[2000005], iv[2000005];
ll c(int i, int j){
	ll res=(fc[i]*iv[j])%mod;
	res=(res*iv[i-j])%mod;
	return res;
}
int32_t main(){
	fc[0]=1ll;
	for(int i=1; i<2000005; i++) fc[i]=(fc[i-1]*i)%mod;
	iv[2000004]=fp(fc[2000004], mod-2);
	for(int i=2000003; i>=0; i--) iv[i]=(iv[i+1]*(i+1))%mod;
	int k, n; cin>>k;
	string s; cin>>s; n=s.size();
	ll ans=0ll;
	for(int i=n; i<=k+n; i++)
		(ans+=(c(k+n, i)*fp(25, k+n-i)))%=mod;
	cout<<ans<<endl;
	return 0;
}