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 int long long 
using namespace std;

const int N = 2e6 + 7, mod = 1e9 + 7;

int POW(int a, int b, int mod) {
	a %= mod; int r = 1;
	for(int i = b; i > 0; i >>= 1) {
		if(i & 1) r = (r * a) % mod;
		a = (a * a) % mod;
	}
	return r;
}

int f[N];


int nCr(int n, int r) {
	if(n < r) return 0;
	return f[n] * POW(f[n - r] * f[r], mod - 2, mod) % mod;
}


int32_t main() {
	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	f[0] = 1;
	for(int i = 1; i < N; i++) {
		f[i] = (f[i - 1] * i) % mod;
	}	
	int k; string s; cin >> k >> s;
	int ans = 0;
	for(int i = 0; i <= k; i++) {
		ans += nCr(k - i + (int)s.size() - 1, (int)s.size() - 1) * (POW(26, i, mod) * POW(25, k - i, mod) % mod) % mod;
		ans %= mod;
		
	}

	cout << ans << endl;
}