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;

const int N=2e6+20,MOD=1e9+7,C=26;

int k,f[N],ie[N];
string s;
long long ans=1;

int mul(int a,int b) {return (1ll*a*b)%MOD;}

int power(int a,int b)
{
	int num=a,ans=1;
	for(int i=0;i<31;i++)
	{
		if(b&(1<<i)) ans=(1ll*ans*num)%MOD;
		num=(1ll*num*num)%MOD;
	}
	return ans;
}

int inverse_euler(int n)
{
	return power(n,MOD-2);
}

int ncr(int n,int r)
{
	return (1LL*f[n]*((1LL*ie[r]*ie[n-r])%MOD))%MOD;
}

void precompute()
{
	f[0]=1;
	for(int i=1;i<N;i++) f[i]=(1LL*f[i-1]*i)%MOD;
	for(int i=0;i<N;i++) ie[i]=inverse_euler(f[i]);
}

int main()
{
	precompute();

	cin>>k>>s;

	int n=k+s.size();
	ans=power(C,n);

	for(int i=0;i<s.size();i++)
	{
		ans=(ans-mul(ncr(n,i),power(C-1,n-i)))%MOD;
		if(ans<0) ans+=MOD;
	}

	printf("%lld",ans);
}