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<cstdio>
#include<iostream>
#include<string>
using ull = unsigned long long;
const static int MOD = 1000000007;
ull RepeatSquaring(ull N, ull P){
	if(P == 0 || N == 1) return 1;
	if(N == -1) return P & 1 ? -1 : 1;
	if(!(P & 1)){
		ull t = RepeatSquaring(N, P >> 1);
		return t*t %MOD;
	}
	return N*RepeatSquaring(N, P - 1) % MOD;
}

int main(){
    ull K;
    scanf("%llu", &K);
    std::string S;
    std::cin >> S;
    ull sz = S.size(), answer = 1, power = 1, cmb = sz;
    for (size_t i = sz; i < K + sz; i++){
        power = power*25 %MOD;
        answer = (answer*26 %MOD + cmb*power %MOD) %MOD;
        cmb = cmb*(i+1) %MOD *RepeatSquaring(i + 2 - sz, MOD-2) %MOD;
    }
    printf("%llu\n", answer);
	return 0;
}