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;
const int N =2000000+5, yzh = 1e9+7;

int k, n, fac[N], ifac[N]; char ch[N];

int quick_pow(int a, int b) {
    int ans = 1;
    while (b) {
        if (b&1) ans = 1ll*a*ans%yzh;
        b >>= 1, a = 1ll*a*a%yzh;
    }
    return ans;
}
int C(int n, int m) {return 1ll*fac[n]*ifac[m]%yzh*ifac[n-m]%yzh; }
int main() {
    scanf("%d%s", &k, ch+1); n = strlen(ch+1);
    ifac[0] = ifac[1] = fac[0] = 1;
    for (int i = 2; i <= n+k; i++) ifac[i] = -1ll*yzh/i*ifac[yzh%i]%yzh;
    for (int i = 1; i <= n+k; i++) {
        fac[i] = 1ll*fac[i-1]*i%yzh;
        ifac[i] = 1ll*ifac[i]*ifac[i-1]%yzh;
    }
    int ans = 0;
    for (int i = 0; i <= k; i++)
        (ans += 1ll*quick_pow(25, k-i)*quick_pow(26, i)%yzh*C(n+k-i-1, n-1)%yzh) %= yzh;
    printf("%d\n", (ans+yzh)%yzh);
    return 0;
}
