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;
#define REP(i, n) for(int i=0; i<(int)(n); i++)
typedef unsigned long long ULL;
const int nMax=2e6+1, MOD=1e9+7;
ULL inv[nMax], fct[nMax], ivf[nMax];
ULL Comb(int n, int r){ return (((fct[n]*ivf[r])%MOD)*ivf[n-r])%MOD; }
ULL pw(ULL a, ULL n){ ULL b=1; while(n){ if(n&1){ b=(b*a)%MOD; } a=(a*a)%MOD; n>>=1; } return b; }
int main(){
inv[1]=fct[0]=fct[1]=ivf[0]=ivf[1]=1;
for(int i=2; i<nMax; i++){ 
  inv[i]=((MOD-MOD/i)*inv[MOD%i])%MOD;
  fct[i]=(fct[i-1]*i)%MOD; ivf[i]=(ivf[i-1]*inv[i])%MOD;
}
ULL K, N, ans=0; string S; cin >> K >> S; N=S.size();
REP(i, K+1){ ans=(ans+(((pw(25, K-i)*pw(26, i))%MOD)*Comb(N+K-i-1, N-1))%MOD)%MOD; }
cout << ans << "\n";
}
