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 sys

def I(): return int(sys.stdin.readline().rstrip())
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

K = I()
n = len(LS2())
mod = 10**9+7

# 完成図は、
# (S[0]以外からなる文字列)S[0](S[1]以外からなる文字列)S[1]…(S[n-1]以外からなる文字列)S[n-1](任意の文字列)
# この表記は一意
# 形式的冪級数で考えると,
# 求めたいものは (1-25x)^(-n)*(1-26x)^(-1) の x^K の係数であり、
# これは、(i+n-1)_C_(n-1)*25^i*26^(K-i) を i=0,…,K にわたって足し合わせたものである

C = [1]
for i in range(1,K+1):
    C.append((C[-1]*(i+n-1)*pow(i,mod-2,mod)) % mod)
# C[i] = (i+n-1)_C_(n-1)

ans = 0
for i in range(K+1):
    ans += C[i]*pow(25,i,mod)*pow(26,K-i,mod)
    ans %= mod

print(ans)