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<vector>
#include<iostream>
#include<algorithm>
#include<chrono>
#include<set>
#include<cstdio>
#include<string>
#include<unordered_map>

using namespace std;
typedef long long ll;
const int mod=1e9+7;

ll qpow(ll a,ll n){
    ll res=1;
    while(n)
    {
        if(n&1) 
          res = res*a%mod;
        a=a*a%mod;
        n >>= 1;
    }
    return res;
}

int n,m;
ll ans,f[2000005]={1}, inv[2000005]={1};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for(int i=1;i<=2e6+3;i++){
        f[i] = f[i-1] * i%mod;
        inv[i] = qpow(f[i],mod-2); //质数模下的逆元，根据费马定理
    }
    int K;
    long long ans = 0;
    string S;
    cin >> K >> S;
    int n = S.length();
    for(int i = 0; i <= K; i++){
        ans = (ans + qpow(26,i)%mod*f[n+K-i-1]%mod*inv[n-1]%mod*inv[K-i]%mod*qpow(25,K-i)%mod)%mod;
    }
    cout << ans << endl;
}