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 intl long long int

vector<intl> fact(2e6+3); 

const intl mod=1e9+7;

intl pow1(intl x,intl y){
	intl res=1;
	while(y){
		if(y%2){
			res*=x;
			res%=mod;
		}
		x*=x;
		x%=mod;
		y/=2;
	}
	return res;
}

void factorial(){
	fact[0]=1;
	for(intl i=1;i<2e6+3;i++){
		fact[i]=i;
		fact[i]*=fact[i-1];
		fact[i]%=mod;
	}
}

intl ncr(intl n,intl r){

	intl n1=fact[n];
	intl n2=fact[n-r];
	intl n3=fact[r];
	n2*=n3;
	n2%=mod;
	n3=pow1(n2,mod-2);
	n1*=n3;
	n1%=mod;
	return n1;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	intl i,j,k;
	factorial();
	cin>>k;
	string s;
	cin>>s;
	intl n=s.length();
	j=pow1(26,k+n);
	intl x=n+k;
	intl j1=0;
	for(i=0;i<n;i++){
		intl tmp1=ncr(x,i);
		intl tmp2=pow1(25,x-i);
		tmp1*=tmp2;
		tmp1%=mod;
		j1+=tmp1;
		j1%=mod;
	}
	j-=j1;
	if(j<0){
		j+=mod;
	}
	cout<<j<<"\n";
}
