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>

const int64_t MOD = 1000000007;
int64_t ff[2000006];

int64_t fact(int n) {
  if (n == 0) return 1;
  if (n == 1) return 1;
  if (ff[n] != 0) return ff[n];
  ff[n] = (fact(n-1) * n) % MOD;
  return ff[n] % MOD;
}

int64_t pm(int64_t a, int64_t b) {
  if (b == 0) return 1;
  if (b == 1) return a % MOD;
  int64_t v = pm(a, b/2) % MOD;
  v = v * v % MOD;
  if (b % 2) {
    return v * a % MOD;
  }
  return v;
}

int main() {
  int64_t ans = 0;
  int N;
  int K;
  std::cin >> K;
  std::string s;
  std::cin >> s;
  N = s.size();

  int64_t st = N + K;
  for (; st >= N; --st) {
    int64_t v = pm(26, N + K - st) * pm(25, st - N) % MOD;
    v = v*fact(st - 1) % MOD;
    v = v*pm(fact(st-N), MOD-2) % MOD;
    v = v*pm(fact(N-1), MOD-2) % MOD;
    ans += v;
    ans = ans % MOD;
  }

  printf("%lld\n", ans % MOD);
}
