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 MOD ((int)1e9+7)
 
using namespace std;

string s;
int n,k;

const int N=2e6+6;

long long fac[N],infac[N];

long long nck(int x,int y)
{
	return (((fac[x]*infac[y])%MOD)*infac[x-y])%MOD;
}

long long poww(long long x,int y)
{
	if(y==0) return 1;
	if(y&1) return (x*poww(x,y-1))%MOD;
	return poww((x*x)%MOD,y/2);
}

int main()
{
	cin >> k >> s;
	n=s.size();
	fac[0]=infac[0]=1;
	for(int i=1;i<N;i++)
	{
		fac[i]=(i*fac[i-1])%MOD;
		infac[i]=poww(fac[i],MOD-2);
	}
	long long ans=0;
	for(int i=n;i<=n+k;i++)
	{
		long long x=poww(25,i-n)*nck(i-1,n-1);
		x%=MOD;
		x*=poww(26,n+k-i);
		x%=MOD; ans+=x; ans%=MOD;
	}
	cout << ans << endl;
}