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<iostream>
using namespace std;
const long mod=1e9+7;
long power(long a,long b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;}
int K;
string S;
long fac[2<<20],inv[2<<20];
long comb(int X,int Y){return fac[X]*inv[Y]%mod*inv[X-Y]%mod;}
int main()
{
	cin>>K>>S;
	int T=K+S.size();
	fac[0]=1;
	for(int i=1;i<=T;i++)fac[i]=fac[i-1]*i%mod;
	inv[T]=power(fac[T],mod-2);
	for(int i=T;i--;)inv[i]=inv[i+1]*(i+1)%mod;
	long ans=0;
	for(int i=S.size();i<=K+S.size();i++)
	{
		ans+=comb(T,i)*power(25,T-i)%mod;
	}
	cout<<ans%mod<<endl;
}
