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 <iostream>
#include <cstdio>
#include <cstring>
#define LL long long
const int MAXN = 2e6 + 5;
const int Mod = 1e9 + 7; 
int n, m;
char str[MAXN];
LL fact[MAXN], inv[MAXN]; 

LL qpow(LL a, int b) {
	LL res = 1;
	for (; b; b >>= 1, a = a * a % Mod)
		if (b & 1) res = a * res % Mod;
	return res;
}

LL C(int n, int m) {
	return fact[n] * inv[n - m] % Mod * inv[m] % Mod;
} 

int main() {
	LL ans = 0;
	scanf("%d%s", &n, str + 1);
	m = strlen(str + 1);
	
	fact[0] = 1;
	for (int i = 1; i <= n + m; i++) fact[i] = fact[i - 1] * i % Mod;
	inv[n + m] = qpow(fact[n + m], Mod - 2);
	for (int i = n + m - 1; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % Mod;
	
	for (int i = 0; i <= n; i++) 
		ans  = (ans + qpow(26, i) * C(n + m - i - 1, m - 1) % Mod * qpow(25, n - i) % Mod) % Mod;
	printf("%lld\n", ans);
}