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 push_back
#define fi first
#define se second
#define eb emplace_back

using namespace std;

typedef pair<int, int> ii;
typedef long long ll;
const int N = 2000007, inf = 0x3f3f3f3f;

const int M = 1e9 + 7;

ll fat[N];
ll fast_pow(ll a, ll b) {
	ll ans = 1;

	while(b) {
		if(b&1) ans = a * ans % M;
		b >>= 1;
		a = a * a % M;
	}
	return ans;
}

ll nchoosek(ll n, ll k) {
	ll den = fat[n - k] * fat[k] % M;
	return fat[n] * fast_pow(den, M - 2) % M;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	fat[0] = 1;
	for(int i = 1; i < N; ++i) fat[i] = fat[i-1] * i % M;

	int k; cin >> k;
	string s; cin >> s;
	int n = s.size();

	ll sum = 0;
	for(int x = 0; x <= k; ++x) {
		sum += (fast_pow(25, k - x) * fast_pow(26, x) % M) * nchoosek(n + k - x - 1, n - 1) % M;
		if(sum >= M) sum -= M;
	}
	cout << sum << endl;
}