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;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,m,n) for(int i=m;i<n;i++)
ll mod=1e9+7;

ll power(ll x,ll n){
    if(n==0) return 1;
    ll res=power(x*x%mod,n/2);
    if(n&1) res=res*x%mod;
    return res;
}

int main(){
  int k;
  string s;
  cin>>k>>s;
  int n=s.size();
  ll a[n+k+1];
  a[0]=1;
  rep(i,1,n+k+1) a[i]=a[i-1]*i%mod;
  ll b[n+k+1];
  b[0]=1;
  rep(i,1,n+k+1) b[i]=power(a[i],1e9+5);
  ll ans=0;
  rep(i,0,k+1){
    ans+=power(25,i)*a[n+k]%mod*b[i]%mod*b[n+k-i]%mod;
    ans%=mod;
  }
  cout<<ans<<endl;
}