Problem:


Score: 600 points

Problem Statement

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

Sample Input 1

5
oof

Sample Output 1

575111451

For example, we can obtain proofend, moonwolf, and onionpuf, while we cannot obtain oofsix, oofelevennn, voxafolt, or fooooooo.

Sample Input 2

37564
whydidyoudesertme

Sample Output 2

318008117



Sample input:
5
oof


Sample output:
575111451

Submission status: Runtime Error

Solution code:
k = int(input())
s = input()
d = pow(26, -1, 10 ** 9 + 7)
res = pow(26, k, 10 ** 9 + 7)
temp = res
for i in range(1, k+1):
    temp *= (i + len(s) - 1) * 25 * pow(i, -1, 10 ** 9 + 7) * d % (10 ** 9 + 7)
    temp %= (10 ** 9 + 7)
    res = (res + temp) % (10 ** 9 + 7)
print(res)

Submission status: Runtime Error

Solution code:
def calc_inv(n, mod_n):
    inv_li = [0] * (n + 2)
    inv_li[0] = 0
    inv_li[1] = 1
    for i in range(2, n + 2):
        q, r = divmod(mod_n, i)
        inv_li[i] = -inv_li[r] * q % mod_n
    return inv_li


MOD = 10**9 + 7
inv = calc_inv(max(K, 26) + 10, MOD)

K = int(input())
S = input()
s_len = len(S)


ans = 0
p = pow(26, K, MOD)

for i in range(1, K + 2):
    ans = (ans + p % MOD) % MOD
    p = p * (s_len + i - 1) * inv[i] * 25 * inv[26] % MOD

print(ans)

Submission status: Runtime Error

Solution code:
k = int(input())
s = str(input())

mod = 1000000007
decided_keta = len(s)
all_keta = len(s) + k

kai_list = [1 for i in range(1000010)]
for i in range(2,len(kai_list)):
    kai_list[i] = (kai_list[i-1]*i)%mod

answer = 0
for last_given_character_posi in range(decided_keta-1,all_keta):
    given_posi_pattern = kai_list[last_given_character_posi]*pow(kai_list[decided_keta-1],mod-2,mod)%mod*pow(kai_list[last_given_character_posi-decided_keta+1],mod-2,mod)%mod
    char_pattern = pow(25,last_given_character_posi-(decided_keta-1),mod)
    rest_char_pattern = pow(26,all_keta-(last_given_character_posi+1),mod)
    answer = (answer + given_posi_pattern*char_pattern%mod*rest_char_pattern%mod)%mod
print(answer)

Submission status: Runtime Error

Solution code:
k = int(input())
s = str(input())

mod = 1000000007
decided_keta = len(s)
all_keta = len(s) + k

kai_list = [1 for i in range(1000010)]
for i in range(2,len(kai_list)):
    kai_list[i] = (kai_list[i-1]*i)%mod

answer = 0
for last_given_character_posi in range(decided_keta-1,all_keta):
    given_posi_pattern = kai_list[last_given_character_posi]*pow(kai_list[decided_keta-1],mod-2,mod)*pow(kai_list[last_given_character_posi-decided_keta+1],mod-2,mod)%mod
    char_pattern = pow(25,last_given_character_posi-(decided_keta-1),mod)
    rest_char_pattern = pow(26,all_keta-(last_given_character_posi+1),mod)
    answer = (answer + given_posi_pattern*char_pattern*rest_char_pattern)%mod
print(answer)

Submission status: Runtime Error

Solution code:
k = int(input())
s = str(input())

mod = 1000000007
decided_keta = len(s)
all_keta = len(s) + k

kai_list = [1 for i in range(1000010)]
for i in range(2,len(kai_list)):
    kai_list[i] = (kai_list[i-1]*i)%mod

answer = 0
for last_given_character_posi in range(decided_keta-1,all_keta):
    given_posi_pattern = kai_list[last_given_character_posi]\
    *pow(kai_list[decided_keta-1],mod-2,mod)*pow(kai_list[last_given_character_posi-decided_keta+1],mod-2,mod)%mod
    char_pattern = pow(25,last_given_character_posi-(decided_keta-1),mod)
    rest_char_pattern = pow(26,all_keta-(last_given_character_posi+1),mod)
    answer = (answer + given_posi_pattern*char_pattern*rest_char_pattern)%mod
print(answer)

Submission status: Runtime Error

Solution code:
MAX = 10**6
MOD = 10**9+7

fac = [0] * (MAX+1)
finv = [0] * (MAX+1)
inv = [0] * (MAX+1)

def comb_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX+1):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i-1] * inv[i] % MOD

def comb(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD


if __name__ == '__main__':
    k = int(input())
    s = input()
    n = len(s)
    comb_init()
    ans = 0
    for i in range(k+1):
        val = comb(i+n-1, n-1)
        val *= pow(25, i, MOD)
        val %= MOD
        val *= pow(26, k-i, MOD)
        val %= MOD
        ans += val
        ans %= MOD
    print(ans)

Submission status: Runtime Error

Solution code:
MAX = 10**6
MOD = 10**9+7

fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX

def comb_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i-1] * inv[i] % MOD

def comb(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD


if __name__ == '__main__':
    k = int(input())
    s = input()
    n = len(s)
    comb_init()
    ans = 0
    for i in range(k+1):
        val = comb(i+n-1, n-1)
        val *= pow(25, i, MOD)
        val %= MOD
        val *= pow(26, k-i, MOD)
        val %= MOD
        ans += val
        ans %= MOD
    print(ans)

Submission status: Runtime Error

Solution code:
k = int(input())
s = len(input())
MOD = 10 ** 9 + 7


def mod_inv(n):
    return pow(n, MOD - 2, MOD)


dp1 = [0 for i in range(s)]
dp1[0] = 25
dp1[1] = 1
dp2 = [0 for i in range(s)]
# 1moji
sum_not_0 = 1
end = 1
# 2moji kara s+k moji

total = pow(26, k + s, MOD)
tmp = pow(25, k + s, MOD)
print(total,tmp)
total = (total - tmp) % MOD

for i in range(0, s-1):
    tmp = ((tmp * ((k+s) - i)) % MOD * mod_inv((i + 1) * 25)) % MOD
#    print(tmp)
    total = (total - tmp) % MOD
print(total)

Submission status: Runtime Error

Solution code:
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


# K 文字追加
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

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

print(ans)

Submission status: Runtime Error

Solution code:
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]  # 逆元テーブル計算用テーブル

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

# K 文字追加
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

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

print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Jun 24 20:53:22 2020

@author: NEC-PCuser
"""

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return fact[n] * factinv[r] * factinv[n-r] % mod

def createPowList(K, mod):
    li25 = [1]
    li26 = [1]
    p25 = 1
    p26 = 1
    for i in range(K + 1):
        p25 *= 25
        p25 %= mod
        li25.append(p25)
        p26 *= 26
        p26 %= mod
        li26.append(p26)
    return li25, li26

p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用


p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

if __name__ == '__main__':
    K = int(input())
    n = len(input())
    mod = 10**9+7 #出力の制限
    #25 25 a 25 25 25 b 25 25  c  26 26
    p25, p26 = createPowList(K, mod)

    ans = 0
    for i in range(0, K + 1):
        ans1 = (p25[i] * cmb(n + i - 1, n - 1, mod)) % mod
        ans2 = (p26[K - i])
        ans += (ans1 * ans2) % mod
    
    print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Jun 24 20:53:22 2020

@author: NEC-PCuser
"""

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return fact[n] * factinv[r] * factinv[n-r] % mod


p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

if __name__ == '__main__':
    K = int(input())
    n = len(input())
    mod = 10**9+7 #出力の制限
    #25 25 a 25 25 25 b 25 25  c  26 26
    
    ans = 0
    for i in range(0, K + 1):
        ans1 = (((25 ** i) % (mod)) * cmb(n + i - 1, n - 1, mod)) % mod
        ans2 = (26 ** (K - i)) % mod
        ans += (ans1 * ans2) % mod
    
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline

mod = 10**9+7
MAX_N = 10**6 + 10

fact = [1]
fact_inv = [0]*(MAX_N+4)
for i in range(MAX_N+3):
    fact.append(fact[-1]*(i+1)%mod)

fact_inv[-1] = pow(fact[-1],mod-2,mod)
for i in range(MAX_N+2,-1,-1):
    fact_inv[i] = fact_inv[i+1]*(i+1)%mod


def mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod

k = int(input())
s = list(input())

n = len(s)-1

res = 0

for i in range(n,n+k+1):
    res = (res + (mod_comb_k(i-1,n-1,mod)*pow(25,i-n,mod)%mod)*pow(26,n+k-i,mod))%mod

print(res)

Submission status: Runtime Error

Solution code:
import math


def main():
    k = int(input())
    s = input()

    len_s = len(s)

    ans = 0
    for i in range(k + 1):
        n = 26 ** (k - i)
        n *= 25 ** i
        f_in1 = math.factorial(i + len_s - 1)
        f_i = math.factorial(i)
        f_n1 = math.factorial(len_s - 1)
        n *= math.floor(f_in1 / (f_i * f_n1))
        ans += n

    print(math.floor(ans % (10**9 + 7)))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

MOD = 10**9+7

fac = [1] * (2 * 10**6 + 10)
f_inv = [1] * (2 * 10**6 + 10)

def prepare(n, mod):
    for i in range(1, n+1):
        fac[i] = (fac[i-1] * i) % mod
    
    f_inv[n] = pow(fac[n], -1, MOD)
    for i in range(n-1, 0, -1):
        f_inv[i] = (f_inv[i+1] * (i+1)) % MOD

def modcmb(n, r, mod):
    if n < 0 or r < 0:
        return 0
    if r > n:
        return 0

    return fac[n] * f_inv[r] * f_inv[n-r] % mod


def main():
    K = int(readline())
    S = readline().strip()
    N = len(S)

    prepare(N + K + 10, MOD)

    inv26 = pow(26, -1, MOD)
    pow26 = pow(26, K, MOD)
    pow25 = 1
    ans = 0
    for i in range(K+1):
        ans += (modcmb(N-1+i, i, MOD) * pow25 * pow26) % MOD
        ans %= MOD

        pow25 *= 25
        pow25 %= MOD
        pow26 *= inv26
        pow26 %= MOD

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6+5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
    
K=int(input())
s=input()
S=len(s)

ans=0
for i in range(K+1):
    ans+=(cmb(i+S-1,S-1,mod)*pow(25,i,mod)*pow(26,K-i,mod))%mod
    ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    mod = 10**9+7
    k = int(input())
    n = len(input())

    @njit(i8[:](i8, i8), cache=True)
    def num_calc(n, mod):
        fact = np.ones(n+1, dtype=np.int64)
        for i in range(2, n+1):
            fact[i] = fact[i-1]*i % mod
        return fact

    @njit(i8[:](i8, i8), cache=True)
    def num_calc2(k, mod):
        power = np.ones(k+1, dtype=np.int64)
        for i in range(1, k+1):
            power[i] = power[i-1]*25 % mod
        return power

    @njit(i8(i8, i8, i8), cache=True)
    def pow(n, k, mod=10**9+7):
        l, now = np.ones(64, np.int64), 1
        l[0] = n
        for i in range(1, 64):
            l[i] = l[i-1]*l[i-1] % mod
        for i in range(64):
            if k & 1:
                now = now*l[i] % mod
            k >>= 1
        return now

    fact = num_calc(n+k, mod)
    nk = fact[n+k]
    fact = fact[n+k:n-1:-1]*fact[:k+1] % mod
    power = (num_calc2(k, mod)*nk) % mod

    print(sum([pow(i, mod-2, mod)*j for i, j in zip(fact, power)]) % mod)


main()

Submission status: Runtime Error

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

mod = 10**9+7               # mod素数
N = 1000002                   # 出力の制限
g1 = [1]*(N+1)              # 元テーブル
g2 = [1]*(N+1)              # 逆元テーブル
for i in range( 2, N + 1 ): # 準備
    g1[i] = ( g1[i-1] * i ) % mod
    g2[i] = ( g2[i-1] * pow(i,mod-2,mod) ) % mod

def nCr(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

def main():
#    mod = 10**9+7
    K = int(input())
    S = input()
    Nk = len(S)
    ret = 0
    pw25 = 1
    pw26 = pow(26,K,mod)
    inv26 = pow(26,mod-2,mod)
    for i in range(K+1):
        ret += nCr(i+Nk-1,i,mod) * pw25 * pw26
        ret %= mod
        pw25 = (pw25*25)%mod
        pw26 = (pw26*inv26)%mod

    print(ret)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

mod = 10**9+7
N = 10**5                   # 出力の制限
g1 = [1]*(N+1)              # 元テーブル
g2 = [1]*(N+1)              # 逆元テーブル
for i in range( 2, N + 1 ): # 準備
    g1[i] = ( g1[i-1] * i ) % mod
    g2[i] = ( g2[i-1] * pow(i,mod-2,mod) ) % mod

def nCr(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

def main():
    K = int(input())
    S = input()
    Nk = len(S)
    ret = 0
    for i in range(K+1):
        ret += nCr(i+Nk-1, Nk-1, mod) * pow(25,i,mod) * pow(26,K-i,mod)
        ret %= mod
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# フェルマーの小定理
K = int(input())
S = input()

m = 1000000007

l = len(S)
result = 0

a = pow(26, K, m)
inv26 = pow(26, -1K, m)
b = 1
c = 1
d = 1
for i in range(K + 1):
    # result += pow(26, K - i, m) * mcomb(len(S) - 1 + i, i) * pow(25, i, m)
    result += a * (b * pow(c, -1, m)) * d
    result %= m
    a *= inv26
    a %= m
    b *= l + i
    b %= m
    c *= i + 1
    c %= m
    d *= 25
    d %= m
print(result)

Submission status: Runtime Error

Solution code:
N = map(int, raw_input())

S = raw_input().strip()
L = len(S)

P = 10**9 + 7

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

finvs[L+N-1] = pow(facts[L+N-1], P-2, P)
for i in xrange(L+N-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

Submission status: Runtime Error

Solution code:
K = int(input())
S = input()
s = len(S)
L = []

mod = 10 ** 9 + 7
N = 10 ** 6
fac = [1, 1]
finv = [1, 1]
inv = [0, 1]

def cmb(n, r):
  return fac[n] * ( finv[r] * finv[n-r] % mod ) % mod
 
for i in range(2, N + 1):
  fac.append( ( fac[-1] * i ) % mod )
  inv.append( mod - ( inv[mod % i] * (mod // i) % mod ) )
  finv.append( finv[-1] * inv[-1]  % mod )

for i in range(K+1):
  L.append( cmb(i+s-1, s-1) * pow(25, i, mod) % mod )

ans = []

for i, x in enumerate(L):
  if i == 0:
    ans.append(x)
  else:
    ans.append( ( ans[i-1]*26%mod + x ) % mod )

print(ans[K])

Submission status: Runtime Error

Solution code:
K = int(input())
S = input()
X = len(S)
mod = 10**9+7

ans = pow(26,K,mod)

Y = 25*pow(26, mod-2, mod)

for i in range(X+1,K+X+1):
   
    temp *= Y
    temp %= mod
    
    temp *= i-1
    temp %= mod
    
    temp *= pow(i-X, mod-2, mod)
    temp %= mod    

    ans += temp
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
K = int(input())
S = input()
X = len(S)
mod = 10**9+7

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6+10
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

ans = 0
for i in range(X,K+X+1):
    temp = 1
    A = i-X
    B = K+X-i
    temp *= cmb(A+X-1,X-1,mod)*power(25,A,mod)
    temp %= mod
    temp *= power(26,B,mod)
    ans += temp
    ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
K = int(input())
S = input()
X = len(S)
mod = 10**9+7

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

ans = 0
for i in range(X,K+X+1):
    temp = 1
    A = i-X
    B = K+X-i
    temp *= cmb(A+X-1,X-1,mod)*power(25,A,mod)
    temp %= mod
    temp *= power(26,B,mod)
    ans += temp
    ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
K = int(input())
S = input()
X = len(S)
mod = 10**9+7

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 3*10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

ans = 0
for i in range(X,K+X+1):
  	temp = 1
    A = i-X
    B = K+X-i
    temp *= cmb(A+X-1,X-1,mod)*power(25,A,mod)
    temp %= mod
    temp *= power(26,B,mod)
    ans += temp
    ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
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

# K 文字追加
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)

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

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

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

print(ans)

Submission status: Runtime Error

Solution code:
m = 10**9 + 7
k = int(input(k)
s = input()

# k, s = 5, 'oof'
# k, s = 37564, 'whydidyoudesertme'
l = len(s) + 1
ans = 1
for i in range(k):
    ans = ans * (l + i) * 26 % m
print(ans)

Submission status: Runtime Error

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=1):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.node_size=len(ls)+1
                self.edges,_=GI(self.node_size,self.node_size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.node_size=int(input())
        else:
            self.node_size=inp_size
        self.edges,_=GI(self.node_size,self.node_size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.node_size=len(ls)+1
        self.edges,_=GI(self.node_size,self.node_size-1,ls,index=index)
        return
 
    def dfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def bfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.popleft()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def parent(self,x):
        return self.dfs(0,func=lambda pr,prv,nx,dist:pr,root_v=-1)
 
    def topological_sort(self,x):  # return topological sort of the tree
        tps=[]
        q=deque([x])
        v=[None]*self.node_size
        v[x]=0
        while q:
            c=q.popleft()
            tps.append(c)
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=0
        return tps
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.node_size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.node_size
        self.ETout=[-1]*self.node_size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        #self.st=SegTree(self.node_size*2-1,self.ETdepth,function=min,ide=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
    def __str__(self):
        return  str(self.edges)
 
    def show(self):
        if all([all([d==1 for nd,d in e]) for e in self.edges]):
            print( [[nd for nd,d in e] for e in self.edges] )
        else:
            print(self)

class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    # return boundary index of r such that func({table[i]} =< x , i in [pos,r]
    def right_bound(self,pos,x):
        k=(self.size-pos).bit_length()
        for j in range(k)[::-1]:
            nx=pos+(1<<j)
            if nx<n and self.query(pos,nx+1)<=x:
                pos+=(1<<j)
        return pos
    
    # return boundary index of l such that func({table[i]} =< x , i in [l,pos]
    def left_bound(self,pos,x):
        k=pos.bit_length()
        for j in range(k)[::-1]:
            nx=pos-(1<<j)
            if 0<=nx and self.query(nx,pos+1)<=x:
                pos-=(1<<j)
        return pos
 
    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)


show_flg=False
show_flg=True


ans=0

k=I()
n=len(input())

x=max(k+1,27)
inv=[0]*x
for i in rep(1,x):
    inv[i]=pow(i,mo-2,mo)

ans=0
cm=1
d5=1
d6=pow(26,k,mo)
for i in rep(k+1):
    #n+i C n * 25*i * 26*(k-i)
    #n+i+1 C n = n+i C n * (n+i+1)/i+1
    ans+=cm*d5*d6
    cm*=(n-1+i+1)*inv[i+1]
    d5*=25
    d6*=inv[26]
    cm%=mo
    d5%=mo
    d6%=mo
    ans%=mo
#    show(i,cm,d5,d6,inv[26])
    
print(ans)

Submission status: Runtime Error

Solution code:
k = int(input())
s = input()
n = len(s)
dp = [0]*(k+1)
dp[0] = 1

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


mod = 10**9+7
N = 2000001
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


ans = 0
for i in range(n, n+k+1):
    ans += cmb(n+k, i) * pow(25, n+k-i, mod)
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
k = int(input())
s = input()

n = len(s)
mod = 10**9+7


def framod(n, mod, a=1):
    for i in range(1, n+1):
        a = a * i % mod
    return a


def power(n, r, mod):
    if r == 0:
        return 1
    if r % 2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r % 2 == 1:
        return n * power(n, r-1, mod) % mod


def comb(n, k, mod):
    a = framod(n, mod)
    b = framod(k, mod)
    c = framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod


com = [1]*k
for i in range(k+1):
    comb[i+1] = comb

a25 = [1]*(k+1)
for i in range(k):
    a25[i+1] = a25[i]*25 % mod
a26 = [1]*(k+1)
for i in range(k):
    a26[i+1] = a26[i]*26 % mod
num = 0
for i in range(0, k+1):
    num = (num+comb(i+n-1, n-1, mod)*a25[i] % mod * a26[k-i]) % mod
print(num)

Submission status: Runtime Error

Solution code:
k = int(input())
s = int(input())
big = 10**9+7
ans = 0
f = len(s)
for i in range(k):
  ans = (ans+26*f+1)%big
  f += 1
print(ans)