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 mxN=2e6+7;
const ll MOD=1e9+7;
ll fact[mxN], inv[mxN], comb;
int k, n;
string s;

ll binpow(ll a, ll b) {
    a%=MOD;
    ll ans=1;
    while (b) {
        if (b&1)
            ans=ans*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return ans;
}

void getfacts() {
    fact[0]=inv[0]=1;
    for (int i=1; i<mxN; ++i) {
        fact[i]=(fact[i-1]*i)%MOD;
        inv[i]=binpow(fact[i], MOD-2);
    }
}

int main(void) {
    cin >> k >> s;
    n=s.size()+k;
    getfacts();
    comb=binpow(26, n);
    for (int i=0; i<s.size(); ++i) {
        ll buf=fact[n]*inv[i]%MOD;
        buf=(buf*inv[n-i])%MOD;
        buf=(buf*binpow(25, n-i))%MOD;
        comb=(MOD*MOD+comb-buf)%MOD;
    }
    cout << comb << '\n';
}
