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>

using namespace std;
using ll = long long;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

const int mod = 1e9 + 7;

ll modpow(ll k, ll n) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * k % mod;
    k = k * k % mod;
    n /= 2;
  }
  return res;
}

int main() {
  int k;
  string s;
  cin >> k >> s;

  int n = s.size();

  ll f[n + k + 1];
  f[0] = 1;
  rep(i, n + k) { f[i + 1] = (i + 1) * f[i] % mod; }

  ll fi[n + k + 1];
  rep(i, n + k + 1) fi[i] = modpow(f[i], mod - 2);

  auto choose = [&](ll x, ll y) {
    return (f[x] * fi[y] % mod) * fi[x - y] % mod;
  };

  ll ans = 0;
  for (int i = 0; i <= k; ++i) {
    ll now = modpow(26, k - i);
    now = now * modpow(25, i) % mod;
    now = now * choose(n - 1 + i, n - 1) % mod;
    ans = (ans + now) % mod;
  }
  cout << ans << endl;
  return 0;
}
