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>
#define int long long
using namespace std;
const int mod=1000000007;
int f[2000010],in[2000010];
int cc(int n,int m){
	int sum=1;
	for(;m;m>>=1,n=n*n%mod)
		if(m&1)
			sum=sum*n%mod;
	return sum;
}
int c(int n,int m){
	return f[n]*in[m]%mod*in[n-m]%mod;
}
signed main(){
	int k;
	int sum=0;
	string s;
	cin>>k>>s;
	f[0]=1;
	in[0]=1;
	for(int i=1;i<k+s.size()+5;i++){
		f[i]=f[i-1]*i%mod;
		in[i]=cc(f[i],mod-2);
	}
	for(int i=0;i<=k;i++){
		sum=(sum+cc(26,i)*cc(25,k-i)%mod*c(k-i+s.size()-1,s.size()-1))%mod;
	}
	cout<<sum<<endl;
	return 0;
}
/*
				A					CCCCCCCCCC                
			   AAA                  C
			  A   A                 C
			 A     A                C
			AAAAAAAAA               C
		   A         A              CCCCCCCCCC
*/