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>
#define X first
#define Y second

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;

const ll INF = 2e18;
const int inf = 1e9+10;
const int maxN = 2e6+10;
const int maxD = 15;
const int maxH = 100; 
const int MOD = 1e9+7;

char s[maxN];
ll h[maxN];
ll power(ll x,ll p)
{
	if(p == 0)
	{
		return 1;
	}
	ll t = power(x,p/2);
	t = t*t%MOD;
	if(p%2 == 1)
	{
		t = t*x%MOD;
	}
	return t;
}
ll C(int n,int m)
{
	ll ans = h[n] * power(h[m],MOD-2) %MOD * power(h[n-m],MOD-2)%MOD;
	return ans;
}
int main()
{

	int k;
	scanf("%d",&k);
	scanf("%s",s+1);
	int n = strlen(s+1);
	int m = n+k;
	h[0] = 1;
	for(int i=1;i<=m;i++)
	{
		h[i] = h[i-1]*i%MOD;
	}
	ll sum = 0;
	for(int i=n;i<=m;i++)
	{
		sum = (sum + C(i-1,n-1) * power(25,i-n)%MOD * power(26,m-i)%MOD)%MOD;
	}
	cout<<sum<<endl;
	return 0;
}