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 ll long long
#define pii pair<int,int>
using namespace std;

const int MXN = 2e6+10;
const int MOD = 1e9 + 7;
int fact[MXN];
int add(int x, int y) {return (x+y) % MOD;}
int mul(int x, int y) {return (x*1ll*y) % MOD;}
int bp(int x, int y) {
	int ans = 1;
	while (y) {
		if (y&1) ans = mul(ans, x);
		x = mul(x, x);
		y /= 2;
	}
	return ans;
}
int inv(int x) {return bp(x, MOD-2);}
int comb(int n, int k) {
	return mul(fact[n], inv(mul(fact[k], fact[n-k])));
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int k;
	cin >> k;
	string s;
	cin >> s;
	int n = s.length();
	fact[0] = 1;
	for (int i=1; i<=n+k; i++) fact[i] = mul(fact[i-1], i);
	int ans = bp(26, n+k);
	int sub = 0;
	for (int i=0; i<n; i++) {
		sub = add(sub, mul(comb(n+k, i), bp(25, n+k-i)));
	}
	cout << (ans+MOD - sub)%MOD;
}