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;

typedef long long int ll;

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

vector < ll > fact (N);

ll pwr (ll a, ll b) {
  ll res = 1;
  while (b > 0) {
    if (b & 1) res = (res * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return res;
}

ll inv (ll a) {
  return pwr (a, mod - 2);
}

ll nCr (int n, int r) {
  return ((((fact[n] * inv (fact[r])) % mod) * inv (fact[n - r])) % mod);
}

int main () {
  ios_base::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);

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

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

  ll ans = 0;
  for (int x = 0; x <= k; x++) {
    ans = (ans + ((((pwr (26, x) * pwr (25, k - x)) % mod) * nCr (k - x + n - 1, n - 1)) % mod)) % mod;
  }

  cout << ans << '\n';
}
