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 int MOD = 1e9+7;
const int MAX_N = 2e6+10;
int K;
string S;

ll fact[MAX_N];
ll invf[MAX_N];

ll powmod(ll x, int y)
{
	ll res=1;
	while(y){
		if(y&1) (res*=x)%=MOD;
		(x*=x)%=MOD;
		y>>=1;
	}
	return res;
}

ll nCk(int n, int k)
{
    if(k<0||k>n) return 0;
    return (((fact[n]*invf[n-k])%MOD)*invf[k])%MOD;
}

void solve()
{
	fact[0]=1;
	for(int i=1;i<MAX_N;++i) fact[i]=1LL*i*fact[i-1]%MOD;
	invf[MAX_N-1]=powmod(fact[MAX_N-1], MOD-2);
	for(int i=MAX_N-2;i>=0;--i) invf[i]=1LL*invf[i+1]*(i+1)%MOD;
	
	ll res = 0;
	const int n = S.length();
	for(int len=0;len<n;++len){
		(res+=1LL*nCk(n+K, len)*powmod(25,n+K-len)%MOD)%=MOD;
	}
	ll ans = (powmod(26,n+K)-res+MOD)%MOD;
	cout<<ans;
}

int main()
{
	cin >> K >> S;
	solve();
	return 0;
}