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 ll long long
const long long mod=1e9+7;
const int maxn=2e6+7;

ll fac[maxn*2+1],inv_fac[maxn*2+1];

ll quickpow(ll x,ll n){
    ll res=1;
    x=x%mod;
    while(n){
        if(n&1)res=(res*x)%mod;
        n>>=1;
        x=(x*x)%mod;
    }
    return res;
}


void init(){
    fac[0]=1;
    for(int i=1;i<=maxn;i++) fac[i]=(fac[i-1]*i)%mod;
    inv_fac[maxn]=quickpow(fac[maxn],mod-2);
    for(int i=maxn-1;i>=0;i--) inv_fac[i]=(inv_fac[i+1]*(i+1))%mod;
}

ll C(int n,int m){
    if(n < 0 || m < 0 || m > n) return 0;
    if(m == 0 || m == n) return 1;
    return fac[n]*inv_fac[n-m]%mod*inv_fac[m]%mod;
}
int main (){
	init();
	int k;cin>>k;
	string ss;cin>>ss;
	int n=ss.size();
	ll ret = quickpow(26,n+k);
	for(int i=0;i<n;i++){
		ll tmp=C(n+k,i)*quickpow(25,n+k-i);
		tmp%=mod;
		ret-=tmp;ret+=mod;ret%=mod;
	}
	cout<<ret%mod<<endl;
	return 0;
}


