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;

const int N = 2e6 + 5;
const ll mod = 1e9 + 7;
int k, n;
string s;
ll f[N], inv[N];

ll pw(ll x, ll i) {
    ll b = 1;
    for(; i; i >>= 1, x = x * x % mod) if(i & 1) b = b * x % mod;
    return b;
}
ll ckn(int n, int k) {
    return f[n] * inv[k] % mod * inv[n - k] % mod;
}

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

    cin >> k >> s;
    n = s.size();
    s = ' ' + s;

    ll ans = 0;
    f[0] = 1;
    for(int i = 1; i <= n + k; ++i) f[i] = f[i - 1] * i % mod;
    inv[n + k] = pw(f[n + k], mod - 2);
    for(int i = n + k; i >= 1; --i) inv[i - 1] = inv[i] * i % mod;
    for(int i = 0; i <= k; ++i) {
        ll tmp = pw(25, k - i) * pw(26, i) % mod * ckn(k - i + n - 1, n - 1) % mod;
        ans = (ans + tmp) % mod;
    }
    cout << ans << '\n';
}
