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;
const int mod=1000000007;

inline ll qpow(ll a,ll n){
    ll res=1;
    while(n){
        if(n&1)res=res*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return res;
}

int n,k;
char s[1000005];
ll f[2000005],inv[2000005];

inline ll C(const ll &n,const ll &r){
    return f[n]*inv[n-r]%mod*inv[r]%mod;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    f[0]=inv[0]=1;
    for(int i=1;i<=2e6;i++){
        f[i]=f[i-1]*i%mod;
        inv[i]=qpow(f[i],mod-2);
    }
    cin>>k>>s+1;
    n=strlen(s+1);
    ll ans=0;
    for(int i=0;i<=k;i++){
        ans+=C(i+n-1,n-1)*qpow(26,k-i)%mod*qpow(25,i)%mod;
    }
    cout<<ans%mod<<endl;

    return 0;
}