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>
char s[1000011];int n,k;const int p=1e9+7;
inline int qpow(int bs,int ex){int ans=1;while(ex){if(ex&1)ans=1ll*ans*bs%p;bs=1ll*bs*bs%p;ex>>=1;}return ans;}
int fac[2000001],ifac[2000001];
int main()
{
	scanf("%d%s",&k,s+1);n=strlen(s+1);int ans=0;
	fac[0]=1;for(int i=1;i<=2e6;++i)fac[i]=1ll*fac[i-1]*i%p;
	ifac[2000000]=qpow(fac[2000000],p-2);for(int i=2e6-1;i>=0;--i)ifac[i]=1ll*ifac[i+1]*(i+1)%p;
	for(int i=0;i<=k;++i)(ans+=1ll*fac[n+k-i-1]*ifac[n-1]%p*ifac[k-i]%p*qpow(26,i)%p*qpow(25,k-i)%p)%=p;printf("%d\n",ans);return 0;
}