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 N=2000005,mod=1000000007;
int f[N]={1};
int qp(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1)
			ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
int c(int n,int m)
{
	return f[n]*qp(f[m],mod-2)%mod*qp(f[n-m],mod-2)%mod;
}
signed main()
{
	ios::sync_with_stdio(false);
	for(int i=1;i<=2000000;i++)
		f[i]=f[i-1]*i%mod;
	int n,k;string s;
	cin>>k>>s;
	n=s.size();
	int ans=0;
	for(int i=n;i<=n+k;i++)
	{
		int zh=qp(26,n+k-i);
		zh=zh*c(i-1,n-1)%mod;
		zh=zh*qp(25,i-n)%mod;
		ans=(ans+zh)%mod;
	}
	cout<<ans<<endl;
	return 0;
}