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>
#include <tuple>
typedef long long int ll;
using namespace std;
#define MAXN 1000001
#define mod 1000000007
ll Pow(ll a, ll n) {
    if (n == 0) return 1;
    if (n % 2) return (a * Pow(a, n - 1)) % mod;
    else {
        ll k = Pow(a, n / 2);
        return (k * k) % mod;
    }
}
ll gyakusuu[MAXN + 1];
int main() {
    // Fn = (n + N - 1)C(N - 1) * 25**(n)
    // Gn = Fn + 26 * Gn-1
    for (int i = 1; i <= MAXN; i++) {
        gyakusuu[i] = Pow(i, mod - 2);
    }
    ll k;
    string s;
    cin >> k >> s;
    ll N = s.length();
    ll g = 1; // n = 0;
    ll f = N * 25; // n = 1;
    for (int i = 1; i <= k; i++) {
        g = (f + 26 * g) % mod;
        f = ( (25 * (i + N) % mod) * gyakusuu[i + 1] % mod ) * f % mod;
    }
    cout << g << endl;
    return 0;
}