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;
using ll = long long;
const ll mod = 1e9+7;
ll fac[2000005];
ll qpow(ll x,ll n)
{
    ll res =1;
    while(n>0)
    {
        if(n&1) res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}
ll C(ll n,ll m){
	return fac[n]*qpow(fac[m] , mod-2)%mod*qpow(fac[n-m] , mod-2)%mod;
}
int main(){
	//freopen("in.txt","r",stdin);
	fac[0] = 1;
	fac[1] = 1;
	for(ll i=2;i<2000002;i++){
		fac[i] = i * fac[i-1];
		fac[i] %= mod;
	}
	ll k;
	cin>>k;
	string ss;
	cin>>ss;
	ll s = ss.size();
	ll ans = 0;
	for(ll i=0;i<s;i++){
		ans += C(k+s , i) * qpow(25 , k+s-i);
		ans %= mod;
	}
	cout<<(qpow(26 , k+s) - ans + mod) % mod<<endl;
	return 0;
}