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 ll;

ll K;
string S;
ll N;
const ll MOD = 1e9 + 7;
vector<ll> Inv, Fact, IFact;
ll Res;

ll choose(ll a, ll b) { return Fact[a] * IFact[b] % MOD * IFact[a - b] % MOD; }
ll power(ll a, ll b) {
  ll res = 1, tmp = a;
  for (ll x = 1; x <= b; x <<= 1) {
    if (b & x) (res *= tmp) %= MOD;
    (tmp *= tmp) %= MOD;
  }
  return res;
}
int main() {
  cin >> K >> S;
  N = S.size();
  Inv.resize(N + K + 1), Fact.resize(N + K + 1), IFact.resize(N + K + 1);
  Inv[1] = Fact[0] = Fact[1] = IFact[0] = IFact[1] = 1;
  for (ll i = 2; i <= N + K; ++i) {
    Inv[i] = MOD - MOD / i * Inv[MOD % i] % MOD;
    Fact[i] = i * Fact[i - 1] % MOD;
    IFact[i] = Inv[i] * IFact[i - 1] % MOD;
  }
  for (ll i = 0; i <= K; ++i) {
    (Res +=
     choose(N - 1 + i, i) * power(25, i) % MOD * power(26, K - i) % MOD) %= MOD;
  }
  cout << Res << endl;
  return 0;
}
