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;

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

ll inv_mod(ll a, ll MOD)
{
    ll b = MOD, u = 1, v = 0;
    while(b){
        ll t = a/b;
        a -= t*b;   swap(a,b);
        u -= t*v;   swap(u,v);
    }
    u %= MOD;
    if(u < 0) u+= MOD;
    return u;
}

int main()
{
    ll i,j;
    ll k;
    string s;
    cin >> k >> s;
    ll n = s.size();
    const ll MOD = 1e9 + 7;
    
    vector<ll> v26(k+1,1);
    vector<ll> v25(k+1,1);
    for(i = 0;i < k;++i){
        v26.at(i+1) = v26.at(i)*26%MOD;
        v25.at(i+1) = v25.at(i)*25%MOD;
    }

    ll tmp = 1;
    ll ans = tmp*v26.at(k-0)%MOD*v25.at(0)%MOD;

    for(i = 1;i <= k;++i){
        tmp = tmp*(n + i - 1)%MOD*inv_mod(i, MOD)%MOD;
        ans += tmp*v26.at(k-i)%MOD*v25.at(i)%MOD;
        ans %= MOD;
    }
    cout << ans << endl;

    return 0;
}