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: Time Limit Exceeded

Solution code:
# フェルマーの小定理
def main():
    from builtins import pow

    K = int(input())
    S = input()

    m = 1000000007

    result = 0
    t = pow(26, K, m)
    u = pow(26, m - 2, m) * 25 % m
    l = len(S)
    for i in range(K + 1):
        # result += pow(26, K - i, m) * mcomb(len(S) - 1 + i, i) * pow(25, i, m)
        result = (result + t) % m
        t = (t * u) % m * (l + i) * pow(i + 1, m - 2, m) % m
    print(result)


main()

Submission status: Time Limit Exceeded

Solution code:
# フェルマーの小定理
def main():
    from builtins import pow

    K = int(input())
    S = input()

    m = 1000000007

    result = 0
    t = pow(26, K, m)
    u = pow(26, m - 2, m) * 25 % m
    l = len(S)
    for i in range(K + 1):
        # result += pow(26, K - i, m) * mcomb(len(S) - 1 + i, i) * pow(25, i, m)
        result += t
        result %= m
        t *= u
        t %= m
        t *= l + i
        t %= m
        t *= pow(i + 1, m - 2, m)
        t %= m
    print(result)


main()

Submission status: Time Limit Exceeded

Solution code:
# フェルマーの小定理
def main():
    from builtins import pow

    K = int(input())
    S = input()

    m = 1000000007

    result = 0
    t = pow(26, K, m)
    u = pow(26, m - 2, m) * 25 % m
    l = len(S)
    for i in range(K + 1):
        # result += pow(26, K - i, m) * mcomb(len(S) - 1 + i, i) * pow(25, i, m)
        result += t
        result %= m
        t = t * u * (l + i) * pow(i + 1, m - 2, m) % m
    print(result)


main()

Submission status: Time Limit Exceeded

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

# nCr(n, r, m)
mod = 1000000007
n = len(s) + k

fac = [1,1] # 階乗 n!
inv = [0,1] # 逆元 1/n
finv = [1,1] # 逆元の階乗 (n^-1)! = (1/n)!

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

def nCr(n, r, m):
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m

# a^n mod m
def modpow(a, n, m):
    x = 1
    while n > 0:
        if n & 1: x *= a
        a *= a; a %= m
        n >>= 1
    return x

n = len(s)
ans = 0
for i in range(k+1):
    a = modpow(25, i, mod)
    b = modpow(26, k-i, mod)
    c = nCr(n-1+i, n-1, mod)
    ans += a * b * c
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# フェルマーの小定理
def main():
    from builtins import pow

    K = int(input())
    S = input()

    m = 1000000007

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


main()

Submission status: Time Limit Exceeded

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

m = 1000000007

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

Submission status: Time Limit Exceeded

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

m = 1000000007

result = 0
a = 1
b = 1

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

Submission status: Time Limit Exceeded

Solution code:
def comb(n,r,m):
	if r == 0: return 1
	return memf[n]*pow(memf[r],m-2,m)*pow(memf[n-r],m-2,m)
def memfact(a):
	temp = 1
	yield temp
	for i in range(1,a+1):
		temp = temp * i % 1000000007
		yield temp

K = int(input())
S = input()
s = len(S)
ans = 0
m = 1000000007
memf = []
for x in memfact(s+K-1):
	memf.append(x)
for i in range(K+1):
	ans = (ans+comb(s+K-i-1,K-i,m)*pow(25,K-i,m)*pow(26,i,m)) % m
print(ans)

Submission status: Time Limit Exceeded

Solution code:
K = int(input())
s = len(input())

mod = 10 ** 9 + 7
N = 2 * 10**6
fac = [1, 1]
finv = [1, 1]
inv = [0, 1]
 
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 )

def cmb(n, r):
  return fac[n] * ( finv[r] * finv[n-r] % mod ) % mod

p25 = [1]
p26 = [1]

for i in range(K):
  p25.append(p25[i]*25%mod)
  p26.append(p26[i]*26%mod)

ans = 0

for i in range(K+1):
  ans += ( cmb(s+K-i-1, s-1) * p25[K-i] % mod ) * p26[i] % mod

print(ans)

Submission status: Time Limit Exceeded

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

temp = pow(26,K,mod)
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: Time Limit Exceeded

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



temp = cmb(X-1,X-1,mod)*power(26,K,mod)
temp %= mod

ans = temp

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: Time Limit Exceeded

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 = 2*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


A = 0
B = K
temp = cmb(A+X-1,X-1,mod)*power(25,A,mod)
temp %= mod
temp *= power(26,B,mod)
temp %= mod

ans = temp

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

    temp *= 25
    temp %= mod
    
    temp *= pow(26, mod-2, mod)
    temp %= mod
    
    temp *= i-1
    temp %= mod
    
    temp *= pow(i-X, mod-2, mod)
    temp %= mod    

    ans += temp
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:


MOD = 10**9+7
factorial = [1]
inverse_factorial = [0]


def modpow(a, p):
    ans = 1
    while p:
        if p&1 == 1:
            ans = (ans*a)%MOD
        a = (a*a)%MOD
        p >>= 1
    return ans


def nCr(n, r):
    if r == 0 or r == n:
        return 1
    return (((factorial[n]*inverse_factorial[n-r])%MOD)*inverse_factorial[r])%MOD


def init_nCr(max_n):
    for i in range(1, 2*max_n+1):
        f = (factorial[-1]*i)%MOD
        factorial.append(f)
        inv_f = modpow(f, MOD-2)
        inverse_factorial.append(inv_f)


def pow(b, p):
    ans = 1
    for _ in range(p):
        ans = (ans*b)%MOD
    return ans


def pow_list(b, p):
    ans = [1]
    for _ in range(p):
        ans.append(ans[-1]*b)
    return ans


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    K = read_int()
    S = len(input().strip())
    init_nCr(K+S)
    T = pow(26, K+S)
    pow_25 = pow_list(25, K+S)
    for i in range(S):
        T = (T-nCr(K+S, i)*pow_25[K+S-i])%MOD
    return T


if __name__ == '__main__':
    print(solve())

Submission status: Time Limit Exceeded

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)
    temp %= mod
    ans += temp
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


MOD = 10 ** 9 + 7
K = int(input())
S = input()
L = len(S)
modFacts, invs = prepare(K + L)

pow25 = [1] * max(L + 1, K + 1)
pow26 = [1] * max(L + 1, K + 1)
for i in range(max(L, K)):
    pow25[i + 1] = (pow25[i] * 25) % MOD
    pow26[i + 1] = (pow26[i] * 26) % MOD

ans = 0
for n in range(L, L + K + 1):
    nonSi = (pow25[n - L] * pow26[L + K - n]) % MOD
    Si = (modFacts[n - 1] * invs[L - 1] * invs[n - 1 - (L - 1)]) % MOD
    ans += nonSi * Si
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


K = int(input())
S = input()
L = len(S)
modFacts, invs = prepare(K + L)

ans = 0
for n in range(L, L + K + 1):
    nonSi = (pow(25, n - L, MOD) * pow(26, L + K - n, MOD)) % MOD
    Si = (modFacts[n - 1] * invs[L - 1] * invs[n - 1 - (L - 1)]) % MOD
    ans += nonSi * Si
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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 = 2*10**6+3
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: Time Limit Exceeded

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: Time Limit Exceeded

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):
    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: Time Limit Exceeded

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 = 2*10**6+3
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):
    A = i-X
    B = K+X-i
    ans += cmb(A+X-1,X-1,mod)*power(25,A,mod)*power(26,B,mod)
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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):
    A = i-X
    B = K+X-i
    ans += cmb(A+X-1,X-1,mod)*power(25,A,mod)*power(26,B,mod)
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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):
    A = i-X
    B = K+X-i
    ans += cmb(A+X-1,X-1,mod)*power(25,A,mod)*power(26,B,mod)
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

m = 1000000007


def make_factorial_table(n):
    result = [0] * (n + 1)
    result[0] = 1
    for i in range(1, n + 1):
        result[i] = result[i - 1] * i % m
    return result


def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], m - 2, m) * pow(fac[k], m - 2, m) % m


fac = make_factorial_table(len(S) + K)

result = 0
for i in range(K + 1):
    result += pow(26, i, m) * mcomb(len(S) - 1 + K - i, len(S) - 1) * pow(25, K - i, m)
    result %= m
print(result)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート


def get_input() -> tuple:
    """
    標準入力の取得.

    Returns:\n
        tuple: 標準入力
    """
    K = int(input())
    S = input()
    return K, S


def comb(n, r):
    """
    組み合わせの総数を求める.

    Args:
        n ([type]): 整数
        r ([type]): 整数

    Returns:
        [type]: 組み合わせの総数
    """
    if n - r < r:
        r = n - r
    if r == 0:
        return 1
    if r == 1:
        return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


def main(K: int, N: int) -> None:
    """
    求解処理.

    Args:
        K (int): 1以上10^6以下の整数
        S (str): 英子文字からなる長さ1以上10^6以下の文字列
    """
    # 求解処理
    ans = 0
    for i in range(K + 1):
        ans += 25**i * comb(i + N - 1, N - 1) * 26**(K - i)

    ans %= 10**9 + 7

    # 結果出力
    print(ans)


if __name__ == "__main__":
    K, S = get_input()
    main(K, len(S))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
from scipy.special import comb


def get_input() -> tuple:
    """
    標準入力の取得.

    Returns:\n
        tuple: 標準入力
    """
    K = int(input())
    S = input()
    return K, S


def main(K: int, S: str) -> None:
    """
    求解処理.

    Args:
        K (int): 1以上10^6以下の整数
        S (str): 英子文字からなる長さ1以上10^6以下の文字列
    """
    # 求解処理
    N = len(S)
    ans = 0
    for i in range(K + 1):
        ans += 25**i * comb(i + N - 1, N - 1, exact=True) * 26**(K - i)

    ans %= 10**9 + 7

    # 結果出力
    print(ans)


if __name__ == "__main__":
    K, S = get_input()
    main(K, S)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
from scipy.special import comb

# 標準入力の取得
K = int(input())
S = input()

# 求解処理
N = len(S)
ans = 0
for i in range(K + 1):
    ans += 25**i * comb(i + N - 1, N - 1, exact=True) * 26**(K - i)

ans %= 10**9 + 7

# 結果出力
print(ans)

Submission status: Time Limit Exceeded

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

def prepare(m, mod=10 ** 9 + 7):
	fac = [1] * (m + 1)
	inv = [1] * (m + 1)
	for i in range(1, m + 1):
		fac[i] = fac[i - 1] * i % mod
	inv[-1] = pow(fac[-1], mod - 2, mod)
	for i in range(m - 1, -1, -1):
		inv[i] = inv[i + 1] * (i + 1) % mod
	return fac, inv

fac, inv = prepare(n+k)

def cmb(n, r):
	assert n >= r >= 0
	return fac[n] * inv[n - r] * inv[r] % mod

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10
    K = II()
    S = input()
    N = len(S)
    def nCr(n,r):
        res = 1
        r = min(r,n-r)
        for i in range(n-r+1,n+1):
            res = res * i % P
        for i in range(2,r+1):
            res = res * pow(i,P-2,P) % P
        return res
    ans = 0
    pow26 = [0] * (K+1)
    pow26[0] = 1
    for i in range(1,K+1):
        pow26[i] = pow26[i-1] * 26 % P
    pow25 = [0] * (K+1)
    pow25[0] = 1
    for i in range(1,K+1):
        pow25[i] = pow25[i-1] * 25 % P
    for t in range(K+1):
        ans += pow26[t]*pow25[K-t]*nCr(N-1+K-t,K-t)
        ans %= P
    print(ans)

    
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10
    K = II()
    S = input()
    N = len(S)
    def nCr(n,r):
        res = 1
        r = min(r,n-r)
        for i in range(n-r+1,n+1):
            res = res * i % P
        for i in range(2,r+1):
            res = res * pow(i,P-2,P) % P
        return res
    ans = 0
    for t in range(K+1):
        ans += pow(26,t,P)*pow(25,K-t,P)*nCr(N-1+K-t,K-t)
        ans %= P
    print(ans)

    
main()

Submission status: Time Limit Exceeded

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


# 逆元の前計算
factorial = [1, 1]
inverse = [1, 1]
invere_base = [0, 1]
for i in range(2, K + N + 1):
    factorial.append((factorial[-1] * i) % MOD)
    invere_base.append((-invere_base[MOD % i] * (MOD // i)) % MOD)
    inverse.append((inverse[-1] * invere_base[-1]) % MOD)


def nCr(n, r):
    if (r < 0 or r > n):
        return 0
    r = min(r, n - r)
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


ans = 0
for i in range(K + 1):
    ans += pow(25, i, MOD) * nCr(i + N - 1, N - 1) * pow(26, K - i, MOD) % MOD
    ans %= MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
def main():
    mod = 10**9+7
    k = int(input())
    n = len(input())
    fact = [1, 1]
    for i in range(2, n+k+1):
        fact.append(fact[-1]*i % mod)
    nk = fact[n+k]
    print(sum([pow(fact[n+k-i]*fact[i] % mod, mod-2, mod)
               * nk*pow(25, i, mod) % mod for i in range(k+1)]) % mod)


main()

Submission status: Time Limit Exceeded

Solution code:
"""
keyword: 二項係数

与えられた文字列sの最後の文字以降は何を置いても(26通り)良い一方で、最後の文字より前は同じ文字は置けない(25通り)
そこで最後の文字より後と前で分けて場合の数を考える


"""

import sys
sys.setrecursionlimit(10**6)

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

mod = 10**9+7

n = len(s)
fact = [1, 1] # あとでnの階乗を求める初期値　[0!, 1!]

# n!を求める
for i in range(2, 2*(10**6)+1):
    fact.append(fact[-1]*i % mod)

# 二項係数nCrを求める nCr = n!/r!(n-r)!
def nCr(n, r, mod=10**9+7):
    return pow(fact[n-r]*fact[r] % mod, mod-2, mod)*fact[n] % mod # modの世界では逆元はpow(x,mod-2)をかけることと同じ

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

for i in range(k+1):
    now = pow(26, k-i, mod) * pow(25, i, mod) * nCr(i+n-1, n-1)
    ans = (ans+now) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
"""
keyword: 二項係数

与えられた文字列sの最後の文字以降は何を置いても(26通り)良い一方で、最後の文字より前は同じ文字は置けない(25通り)
そこで最後の文字より後と前で分けて場合の数を考える


"""

import sys
sys.setrecursionlimit(10**6)

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

mod = 10**9+7

n = len(s)
fact = [1, 1] # あとでnの階乗を求める初期値　[0!, 1!]

# n!を求める
for i in range(2, 2*(10**6)+1):
    fact.append(fact[-1]*i % mod)

# 二項係数nCrを求める nCr = n!/r!(n-r)!
def nCr(n, r, mod=10**9+7):
    return pow(fact[n-r]*fact[r] % mod, mod-2, mod)*fact[n] % mod # modの世界では逆元はpow(x,mod-2)をかけることと同じ

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

for i in range(k+1):
    now = 26**(k-i)*25**i*nCr(i+n-1, n-1) % mod
    ans = (ans+now) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
"""
keyword: 二項係数

与えられた文字列sの最後の文字以降は何を置いても(26通り)良い一方で、最後の文字より前は同じ文字は置けない(25通り)
そこで最後の文字より後と前で分けて場合の数を考える


"""

import sys
sys.setrecursionlimit(10**6)

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

mod = 10**9+7

n = len(s)
fact = [1, 1] # あとでnの階乗を求める初期値　[0!, 1!]

# n!を求める
for i in range(2, 2*(10**6)+1):
    fact.append(fact[-1]*i % mod)

# 二項係数nCrを求める nCr = n!/r!(n-r)!
def nCr(n, r, mod=10**9+7):
    return pow(fact[n-r]*fact[r] % mod, mod-2, mod)*fact[n] % mod # modの世界では逆元はpow(x,mod-2)をかけることと同じ

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

for i in range(k+1):
    now = 26**(k-i) % mod
    now *= 25**i % mod
    now *= nCr(i+n-1, n-1) % mod
    ans += now % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class nCrMod():
    def __init__(self, mod):
        self.mod = mod
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]

    def prep(self, n):
        mod = self.mod
        f, fi = self.fac[-1], self.finv[-1]
        for i in range(len(self.fac), n + 1):
            fn = f * i % mod
            v = -self.inv[mod % i] * (mod // i) % mod
            fin = fi * v % mod
            f, fi = fn, fin
            self.fac.append(f)
            self.finv.append(fi)
            self.inv.append(v)

    def __call__(self, n, r):
        if len(self.fac) <= n:
            self.prep(n)
        return self.fac[n] * self.finv[r] * self.finv[n - r] % self.mod


def main():
    K = int(input())
    S = input()
    N = len(S)
    mod = 10**9 + 7
    nCr = nCrMod(mod)
    r = 0
    for i in range(K + 1):
        r = (r + pow(25, i, mod) * pow(26, K - i, mod) * nCr(N + i - 1, N - 1)) % mod
    return r

        
print(main())

Submission status: Time Limit Exceeded

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

def nCr(n, r, mod):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    factinv.append((factinv[-1] * inv[-1]) % MOD)

k = int(input())
s = len(input())

ans = 0
for i in range(k+1):
    ansp =  pow(26,i,MOD) * pow(25,k-i,MOD) * nCr(s+k-1-i,s-1,MOD) % MOD 
    ans = (ans + ansp) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

sys.setrecursionlimit(10**6)
input = sys.stdin.readline
#read = sys.stdin.buffer.read

MOD = pow(10, 9)+7

def combi(n, k, MOD):
    numer = 1
    for i in range(n, n-k, -1):
        numer *= i
        numer %= MOD
    denom = 1
    for j in range(k, 0, -1):
        denom *= j
        denom %= MOD
    return (numer*(pow(denom, MOD-2, MOD)))%MOD

def main():
    K = int(input())
    S = input()[:-1]
    lenS = len(S)
    ans = 0
    for i in range(lenS, lenS+K+1):
        k = min(i-lenS, lenS-1)
        ans += combi(i-1, k, MOD)*pow(25, i-lenS, MOD)*pow(26, lenS+K-i, MOD)
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 2 * (10 ** 6) + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 2 * (10 ** 6):
            return self.cmbl(n, r)
        return self.cmbr(n, r)

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

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def main():
    K = int(input())
    S = input()
    l = len(S)
    mod = 10**9 + 7
    c = cmbs(mod)
    r = 0
    x25 = 1
    x26 = pow(26, K, mod)
    inv26 = pow(26, mod-2, mod)
    for i in range(K+1):
        r = (r + c.cmb(l+i-1, i) * x25 * x26) % mod
        x25 = x25 * 25 % mod
        x26 = x26 * inv26 % mod
    return r % mod
print(main())

Submission status: Time Limit Exceeded

Solution code:
class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 10 ** 6 + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 10 ** 6:
            return self.cmbl(n, r)
        return self.cmbr(n, r)

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

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def main():
    K = int(input())
    S = input()
    l = len(S)
    mod = 10**9 + 7
    c = cmbs(mod)
    r = 0
    x25 = 1
    x26 = pow(26, K, mod)
    inv26 = pow(26, mod-2, mod)
    for i in range(K+1):
        r = (r + c.cmb(l+i-1, i) * x25 * x26) % mod
        x25 = x25 * 25 % mod
        x26 = x26 * inv26 % mod
    return r % mod
print(main())