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;
const int mod = 1000000007;
int k;
string s;
int n;
ll F[2000005];
ll I[2000005];
ll E26[2000005];
ll E25[2000005];
ll exp(ll a, ll x){
    if (x == 0) return 1ll;
    ll p = exp(a,x/2);
    p = (p*p)%mod;
    if (x & 1) p = (p*a)%mod;
    return p;
}
ll C(ll n ,ll k){
    return ((F[n]*I[n-k])%mod*I[k])%mod;
}
ll ans = 0;
int main(){
    cin >> k >> s;
    n = (int)s.size();
    F[0] = I[0] = E25[0] = E26[0] = 1;
    for (int i = 1; i <= 2000000; i++){
        F[i] = (F[i-1]*i)%mod;
        I[i] = exp(F[i],mod-2);
        E25[i] = (E25[i-1]*25ll)%mod;
        E26[i] = (E26[i-1]*26ll)%mod;
    }
    for (int i = n-1; i < n+k; i++){
        ans += (((C(i,n-1)*E25[i-n+1])%mod)*E26[(n+k)-i-1])%mod;
        ans %= mod;
    }
    printf("%lld",ans);
}
