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
#import <bits/stdc++.h>
using namespace std;
 
#define MOD 1000000007ll
 
int k;
long long res = 0;
long long fac[2000005];
string s;

long long inv(long long n) {
	long long p = 1000000005ll;
	long long ans = 1; 
    while(p > 0) {
        if(p%2) ans = (ans*n)%MOD; 
        p /= 2; 
        n = (n*n)%MOD;
    } 
   
    return ans; 
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> k >> s;
	
	fac[0] = 1;
	long long pow = 1;
	long long pow2 = 1;
	for(int i = 0; i < k; i++) pow = (pow*25)%MOD;
	for(int i = 0; i < k+s.length(); i++) fac[i+1] = (fac[i]*(i+1))%MOD;
	
	for(int i = 0; i < k+1; i++) {
		res = (res+((((((fac[k+s.length()-i-1]*inv(fac[s.length()-1])%MOD)*inv(fac[k-i]))%MOD)*pow)%MOD)*pow2)%MOD)%MOD;
		pow2 = (pow2*26)%MOD;
		pow = (pow*inv(25))%MOD;
	}
	
	cout << res << endl;
}
