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 = 1e9+7;
ll f1[2000005], f2[2000005];
char s[1000005];
ll pow2(ll a, ll b){
    ll ans = 1;
    while(b){
        if(b%2 == 1) ans = ans*a%mod;
        a = a*a%mod;
        b/=2;
    }
    return ans;
}
ll nCr(int a, int b){
    return f1[a]*1ll*f2[b]%mod*f2[a-b]%mod;
}
int main(){
    f1[0] = f2[0] = 1;
    for(int i=1;i<=2000000;i++){
        f1[i] = f1[i-1]*i%mod;
        f2[i] = pow2(f1[i], mod-2);
    }
    int k, n;
    scanf("%d%s", &k, s+1);
    n = strlen(s+1);
    k += n;
    ll ans = 0;
    for(int i=n;i<=k;i++){
        ll res = nCr(i-1, n-1)*1ll*pow2(26, k-i)%mod*pow2(25, i-1-(n-1))%mod;
        ans = (ans + res)%mod;
    }
    printf("%lld\n", ans);
}