Problem: 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).

Submission attempts (in order):
import sys

K = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip('\n')

# ## COMBINATION (MOD) ###
N_MAX = 10**6  
MOD = 10**9 + 7

inv = [0] * (N_MAX + 2)
inv[0] = 0  
inv[1] = 1

for i in range(2, N_MAX + 2):
    q, r = divmod(MOD, i)
    inv[i] = -inv[r] * q % MOD



ans = 0

ln = len(S)

p = pow(26, K, MOD)

st = time.time()
for i in range(1, K + 2):

    ans += p % MOD
    ans %= MOD

    # pre
    p = p * (ln + i - 1) * inv[i] * 25 * inv[26] % MOD

    
    # s2 = (s2 * inv[26]) % MOD
en = time.time()

print(ans)

import sys
import time


K = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip('\n')

# ## COMBINATION (MOD) ###
N_MAX = 10**6  
MOD = 10**9 + 7

st = time.time()
inv = [0] * (N_MAX + 2)
inv[0] = 0  
inv[1] = 1

for i in range(2, N_MAX + 2):
    q, r = divmod(MOD, i)
    inv[i] = -inv[r] * q % MOD

en = time.time()
print(en-st)


ans = 0

ln = len(S)

p = pow(26, K, MOD)

st = time.time()
for i in range(1, K + 2):

    ans += p % MOD
    ans %= MOD

    # pre
    p = p * (ln + i - 1) * inv[i] * 25 * inv[26] % MOD

    
    # s2 = (s2 * inv[26]) % MOD
en = time.time()

print(ans)
print(en-st)

import sys

K = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip('\n')

# ## COMBINATION (MOD) ###
N_MAX = 2*10**6  
MOD = 10**9 + 7

fac = [1, 1]  
facinv = [1, 1]  
inv = [0, 1]  計算用テーブル

for i in range(2, N_MAX + 1):
    fac.append((fac[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    facinv.append((facinv[-1] * inv[-1]) % MOD)


def cmb(n, r):
    if (r < 0 or r > n):
        return 0
    # r = min(r, n-r)
    return fac[n] * facinv[r] * facinv[n - r] % MOD


ans = 0

ln = len(S)

for i in range(ln, ln+K+1):

    # pre
    p = i - 1
    p1 = cmb(p, ln - 1)
    p2 = pow(25, p - (ln - 1), MOD)

    
    s = (ln + K) - i
    s2 = pow(26, s, MOD)

    ans += p1*p2*s2 % MOD
    ans %= MOD

    # print(p, p1,p2, s, s2)

print(ans)

import sys

K = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip('\n')

# ## COMBINATION (MOD) ###
N_MAX = 10**6  
MOD = 10**9 + 7

fac = [1, 1]  
facinv = [1, 1]  
inv = [0, 1]  計算用テーブル

for i in range(2, N_MAX + 1):
    fac.append((fac[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    facinv.append((facinv[-1] * inv[-1]) % MOD)


def cmb(n, r):
    if (r < 0 or r > n):
        return 0
    # r = min(r, n-r)
    return fac[n] * facinv[r] * facinv[n - r] % MOD


ans = 0

ln = len(S)

for i in range(ln,ln+K+1):

    # pre
    p = i - 1
    p1 = cmb(p, ln - 1)
    p2 = pow(25, p - (ln - 1), MOD)

    
    s = (ln + K) - i
    s2 = pow(26, s, MOD)

    ans += p1*p2*s2 % MOD
    ans %= MOD

    # print(p, p1,p2, s, s2)

print(ans)

import sys

K = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip('\n')

# ## COMBINATION (MOD) ###
N_MAX = 10**6  
MOD = 10**9 + 7

inv = [0, 1]  
K = max(K, 26)
for i in range(2, K + 2):
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)


ans = 0

ln = len(S)

p1 = 1
p2 = 1
s2 = pow(26, K, MOD)

for i in range(1, K + 2):

    ans += (p1 * p2 * s2) % MOD
    ans %= MOD

    # print(p1, p2, s2)

    # pre
    p1 = (p1 * (ln + i - 1) * inv[i]) % MOD
    p2 = (p2 * 25) % MOD

    
    s2 = (s2 * inv[26]) % MOD

print(ans)


import sys

K = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip('\n')

# ## COMBINATION (MOD) ###
N_MAX = 10**6  
MOD = 10**9 + 7

inv = [0] * (N_MAX + 2)
inv[0] = 0  
inv[1] = 1

for i in range(2, N_MAX + 2):
    q, r = divmod(MOD, i)
    inv[i] = -inv[r] * q % MOD



ans = 0

ln = len(S)

p = pow(26, K, MOD)

for i in range(1, K + 2):

    ans += p % MOD
    ans %= MOD

    # pre
    p = p * (ln + i - 1) * inv[i] * 25 * inv[26] % MOD

    
    # s2 = (s2 * inv[26]) % MOD

print(ans)


Verdicts: Runtime Error

Wrong Answer

Time Limit Exceeded

Runtime Error

Wrong Answer

Accepted