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 N = 1000005;
const int MOD = 1000000007;

int n, inv[N * 2], fac[N * 2], m;
char str[N];

int ksm(int x, int y)
{
	int ans = 1;
	while (y)
	{
		if (y & 1) ans = (LL)ans * x % MOD;
		x = (LL)x * x % MOD; y >>= 1;
	}
	return ans;
}

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

int main()
{
	scanf("%d", &n);
	scanf("%s", str + 1);
	m = strlen(str + 1);
	fac[0] = fac[1] = inv[0] = inv[1] = 1;
	for (int i = 2; i <= n + m; i++) fac[i] = (LL)fac[i - 1] * i % MOD, inv[i] = (LL)(MOD - MOD / i) * inv[MOD % i] % MOD;
	for (int i = 2; i <= n + m; i++) inv[i] = (LL)inv[i - 1] * inv[i] % MOD;
	int ans = 0;
	for (int i = 0; i <= n; i++)
		(ans += (LL)ksm(26, i) * C(n + m - i - 1, m - 1) % MOD * ksm(25, n - i) % MOD) %= MOD;
	printf("%d\n", ans);
	return 0;
}