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 Sz(a) ((int)(a).size())
const int maxn = 2000009;
const int MOD = 1e9 + 7;
int64_t fac[maxn],invfac[maxn];
int64_t pw(int64_t a,int64_t b){
  int64_t c=1;
  while(b){
    if(b&1ll)c=c*a%MOD;
    b>>=1;
    a=a*a%MOD;
  }
  return c;
}
int64_t C(int a,int b){
  return fac[a]*invfac[b]%MOD*invfac[a-b]%MOD;
}
int main(){
#ifdef LOCAL
  freopen("a.in", "r", stdin);
#endif
  ios_base::sync_with_stdio(false),cout.tie(0),cin.tie(0);
  fac[0]=1;
  for(int i=1;i<maxn;++i)fac[i]=fac[i-1]*i%MOD;
  invfac[maxn-1]=pw(fac[maxn-1],MOD-2);
  for(int i=maxn-2;i>=0;--i)invfac[i]=invfac[i+1]*(i+1)%MOD;
  int K,n;
  string s;cin>>K>>s;
  n=Sz(s);
  int64_t ans=1,deg=1;
  for(int i=0;i<K;++i){
    deg=deg*25%MOD;
    ans=(ans*26+C(n+i,n-1)*deg)%MOD;
  }
  cout<<ans<<"\n";
  
  return 0;
}
//2020.06.23 19:49:09
