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 MAXN=2e6+10,MOD=1e9+7;
ll K,Fac[MAXN],InF[MAXN],Len;
string s;
inline ll fpow(ll a,ll x){
    ll ans=1;
    for(;x;x>>=1,a=a*a%MOD) if(x&1) ans=ans*a%MOD;
    return ans;
}
inline void pre(){
    (cin>>K).get();
    getline(cin,s);
    Len=s.size();
    Fac[0]=1;
    for(int i=1;i<=2e6;i++)
        Fac[i]=Fac[i-1]*i%MOD;
    InF[int(2e6)]=fpow(Fac[int(2e6)],MOD-2);
    for(int i=2e6-1;i>=0;i--)
        InF[i]=InF[i+1]*(i+1)%MOD;
}
inline ll C(ll n ,ll m){
    return (n<m)?0:Fac[n]*InF[m]%MOD*InF[n-m]%MOD;
}
int main(){
    pre();
    ll Sum=0;
    for(int i=0;i<=K;i++)
        Sum+=fpow(26,i)*C(K-i+Len-1,Len-1)%MOD*fpow(25,K-i)%MOD;
    cout<<(Sum%=MOD);
    return 0;
}