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<cstdio>
#include<cstring>
#define P 1000000007
#define N 2000005

int n,m;
char s[N];

int fac[N],inv[N],pw1[N],pw2[N];

int ans;

int main(){
	scanf("%d%s",&n,s+1);
	m=strlen(s+1);
	n+=m;
	fac[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=1ll*fac[i-1]*i%P;
	inv[0]=inv[1]=1;
	for(int i=2;i<=n;i++)
		inv[i]=(P-1ll*P/i*inv[P%i]%P)%P;
	for(int i=2;i<=n;i++)
		inv[i]=1ll*inv[i-1]*inv[i]%P;
	pw1[m]=1;
	for(int i=m+1;i<=n;i++)
		pw1[i]=1ll*pw1[i-1]*25%P;
	pw2[n]=1;
	for(int i=n-1;i;i--)
		pw2[i]=1ll*pw2[i+1]*26%P;
	for(int i=m;i<=n;i++)
		ans=(ans+1ll*fac[i-1]*inv[m-1]%P*inv[i-m]%P*pw1[i]%P*pw2[i]%P)%P;
	printf("%d",ans);
}