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 int long long

const int mod=1e9+7,N=3e6+9;
int fac[N],ifac[N];

int pw(int a,int t=mod-2){
    int x=1;
    while(t>0){
        if(t&1)x=x*a%mod;
        a=a*a%mod,t>>=1;
    }
    return x;
}
int C(int n,int r){
    if(r<0 or r>n)return 0;
    return fac[n]*ifac[r]%mod*ifac[n-r]%mod;
}
int32_t main(){
    ios::sync_with_stdio(0),cin.tie(0);
    fac[0]=ifac[0]=1;
    for(int i=1;i<N;i++){
        fac[i]=i*fac[i-1]%mod;
        ifac[i]=pw(fac[i]);
    }
    int k;
    string st;
    cin >> k >> st;
    int m=(int)st.size()+k,n=(int)st.size(),ans=0;
    int x=1,y=pw(n,m-n),iv=pw(n);
    for(int i=n;i<=m;i++){
        int t=C(i-1,n-1)*pw(25,i-n)%mod*pw(26,m-i)%mod;
        ans=(ans+t)%mod;
    }
    cout << ans << '\n';
}
