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 mod = 1e9+7;
const int N = 1e6+5;
char s[N];
ll fact[2*N];

ll binpow(ll a, ll b) {
	ll ret = 1; a %= mod;
	while (b) {
		if (b & 1) ret = ret * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ret % mod;
}

ll c(int n, int k) {
	return (fact[n] * (binpow(fact[k], mod-2) * binpow(fact[n-k], mod-2) % mod)) % mod;
}

int main()
{
	int k; scanf("%d%s", &k, s);
	ll ans = 0;
	int n = strlen(s);
	fact[0] = 1;
	for (int i = 1; i <= n+k-1; i++) {
		fact[i] = (fact[i-1] * i) % mod;
	}
	for (int i = 0; i <= k; i++) {
		ans = (ans + (c(n+k-i-1, n-1) * (binpow(25, k-i) * binpow(26, i) % mod) % mod)) % mod;
	}
	printf("%lld\n", ans);
	return 0;
}