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
K = int(raw_input())
S = raw_input().strip()
L = len(S)

P = 10**9 + 7

facts = [0 for _ in xrange(L + K)]
finvs = [0 for _ in xrange(L + K)]
facts[0] = 1
for i in xrange(1, L+K):
  facts[i] = (i*facts[i-1]) % P

finvs[L+K-1] = pow(facts[L+K-1], P-2, P)
for i in xrange(L+K-2, -1, -1):
  finvs[i] = (finvs[i+1]*(i+1)) % P

ans = 0
for k in xrange(0, K+1):
  ncr = (facts[k+L-1]*finvs[k]*finvs[L-1]) % P
  ans += ncr * pow(25, k, P) * pow(26, K-k, P)
  ans %= P

print ans
