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
// Copyright 2020 yaito3014
#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("O3")
int main() {
  using namespace std;
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int K;
  cin >> K;
  string S;
  cin >> S;
  const int N = K + S.length();
  constexpr int kMod = 1000000007;
  auto modpow = [&](long long a, int b) {
  	long long r = 1;
  	for (; b > 0; b /= 2) {
  		if (b % 2) r = r * a % kMod;
  		a = a * a % kMod;
  	}
  	return r;
  };
  auto inv = [&](int a) { return modpow(a, kMod - 2); };
  vector<long long> fact(N + 1, 1);
  for (int i = 0; i < N; ++i) fact[i + 1] = fact[i] * (i + 1) % kMod;
  auto c = [&](int n, int r){
  	return fact[n] * inv(fact[n-r] * fact[r] % kMod) % kMod;
  };
  int ans = 0;
  for (int i = 0; i <= K; ++i) {
  	ans += modpow(26, i) * c(N-i-1, N-K-1) % kMod * modpow(25, K-i) % kMod;
  	ans %= kMod;
  }
  cout << ans << '\n';
}
