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>
#define pb emplace_back
using namespace std;
using ll = long long;
const int maxn = 1000010<<1, p = 1e9+7;
ll p25[maxn]{1}, fa[maxn], fainv[maxn], inv[maxn];
void init() {
	for (int i : {0, 1} )fa[i] = fainv[i] = inv[i] = 1;
	for (int i = 2;i < maxn;++i) {
		fa[i] = fa[i-1] * i % p;
		inv[i] = (p - p/i) * inv[p % i] % p;
		fainv[i] = fainv[i-1] * inv[i] % p;
	}
	for (int i = 1;i < maxn;++i) p25[i] = p25[i-1] * 25 % p;
}
#define C(i, j) (fa[i] * fainv[j] % p * fainv[(i)-(j)] % p)
int k, n;
char w[maxn];
ll CAL() {
}


signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	init();
	cin >> k >> w;
	n = strlen(w);
	ll res = 0;
	for (int i = n;i <= n+k;++i) {
		res = (res + p25[n+k-i] * C(n+k, i) % p) % p;
	}
	cout << res << '\n';
}
