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>
#define ll long long 
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pii pair<int,int>
using namespace std;
const int mod=1e9+7; 
const int N=2e6+3;
ll k,fact[N];

ll modpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b%2)ans=ans*a%mod;
        a=a*a%mod;
        b=b/2;
    }
    return ans%mod;
}

void factor(){
    fact[0]=1;
    for(int i=1;i<N;i++)fact[i]=fact[i-1]*i%mod;
}


ll cal(ll x,ll p){
    return fact[x]*modpow(fact[p],(mod-2))%mod*modpow(fact[x-p],(mod-2))%mod;
}

int main(){
    fast factor();
    cin>>k;
    string s;cin>>s;
    int p=s.size();
    ll ans=0;
    for(int i=p;i<=p+k;i++){
        ll temp=cal(i-1,p-1)*modpow(25,i-p)%mod*modpow(26,k+p-i);
        ans=(ans+temp)%mod;
    }
    cout<<ans;
    return 0;
}