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 mod = 1e9+7;
ll kai[(1<<21)];
ll dp[(1<<21)];
void init() {
    kai[0] = 1;
    kai[1] = 1;
    for (ll i = 2; i < (1 << 21); i++) {
        kai[i] = kai[i - 1] * i % mod;
    }
}

ll mp(ll a, ll b) {
    if (b == 0) return 1LL;
    ll ret = mp(a,b/2);
    ret *= ret;
    ret %= mod;
    if (b&1) ret *= a;
    return ret % mod;
}

ll inv(ll k) {
    return mp(k,mod-2);
}

ll c(ll n, ll k) {
    if (k == 0) return 1;
    if (n == k) return 1;
    return kai[n] * inv(kai[k]) % mod * inv(kai[n-k]) % mod;
}

int main() {
    init();
    int k;
    string s;
    cin >> k >> s;
    int n = s.size();
    dp[n] = 1LL;
    for (ll i = n + 1; i <= n + k; i++) {
        dp[i] = dp[i-1] * 26LL % mod;
        dp[i] += c(i-1,n-1) * mp(25LL,i-n);
        dp[i] %= mod;
    }
    cout << dp[n+k] << endl;
    return 0;
}