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 solve(K, N):
    mod = 10**9 + 7
    T = [0] * (N + 1)
    T[0] = 1
    for i in range(K + N):
        T[N] = (T[N - 1] + T[N] * 26) % mod
        for j in reversed(range(1, N)):
            T[j] = (T[j - 1]  + T[j] * 25) % mod
        T[0] = (T[0] * 25) % mod
    return T[-1] % mod

def main():
    K = int(input())
    S = input()
    return solve(K, len(S))
        
print(main())

Submission status: Time Limit Exceeded

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

A = list(map(ord,S))

def dpinit(ps, val=0):
    res = [val for i in [0]*ps[-1]]
    for i in ps[:-1][::-1]:
        res = [res[:] for k in [0]*i]
    return res

M = K+len(S)
dp = dpinit((M+1,len(S)+1))

dp[0][0] = 1

for i in range(1,M+1):
    for j in range(len(S)+1):
        dp[i][j] += dp[i-1][j]*25
        dp[i][j] %= MOD
        if j+1 <= len(S):
            dp[i][j+1] += dp[i-1][j]
            dp[i][j+1] %= MOD
    dp[i][len(S)] += dp[i-1][len(S)]
    dp[i][len(S)] %= MOD

print(dp[M][len(S)])

Submission status: Time Limit Exceeded

Solution code:
class Combination:
    """
    SIZEが10^6程度以下の二項係数を何回も呼び出したいときに使う
    使い方:
    comb = Combination(SIZE, MOD)
    comb(10, 3) => 120
    """

    def __init__(self, N, MOD=10 ** 9 + 7):
        self.MOD = MOD
        self.fact, self.inv = self._make_factorial_list(N)

    def __call__(self, n, k):
        if k < 0 or k > n:
            return 0
        res = self.fact[n] * self.inv[k] % self.MOD
        res = res * self.inv[n - k] % self.MOD
        return res

    def _make_factorial_list(self, N):
        fact = [1] * (N + 1)
        inv = [1] * (N + 1)
        MOD = self.MOD
        for i in range(1, N + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            inv[i - 1] = (inv[i] * i) % MOD
        return fact, inv


mod = 10 ** 9 + 7
U = 2 * 10 ** 6 + 10
comb = Combination(U, mod)
pow26 = [1] * U
pow25 = [1] * U
for i in range(1, U):
    pow25[i] = pow25[i - 1] * 25 % mod
    pow26[i] = pow26[i - 1] * 26 % mod

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

ans = 0
for i in range(K + 1):
    res = K - i
    pos = comb(N - 1 + i, i)
    tmp = pow26[res] * pos % mod * pow25[i] % mod
    ans = (ans + tmp) % mod
print(ans)

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7
K = int(input())
S = input().rstrip()

N = K + len(S)
fact = [1] * (N+1)
fact_inv = [1] * (N+1)
for i in range(1, N+1):
    fact[i] = i * fact[i-1] % mod
fact_inv[N] = pow(fact[N], mod-2, mod)
for i in range(1, N+1)[::-1]:
    fact_inv[i-1] = i * fact_inv[i] % mod
comb = lambda n, k: fact[n] * fact_inv[k] * fact_inv[n-k] % mod

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

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

def combinations_count(n, r):
    ''' 組み合わせ '''
    return factorial(n) // (factorial(n - r) * factorial(r))

#print(combinations_count(5, 2))
def modpow(a, n, MOD):
  res = 1
  while (n > 0):
    if (n & 1):
      res = res * a % MOD
    a = a * a % MOD
    n >>= 1
  return res
 

K = int(input())
S = str(input())
mod = 10 ** 9 + 7
N = len(S)
L = N + K

ans = 0
for i in range(K + 1):
  p = N + K - i - 1
  now = combinations_count(p, N - 1) % mod
  a = pow(25, K - i, mod)
  b = pow(26, i, mod)
  c = a * b % mod
  ans += now * c % mod
  ans = ans % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
K = int(input())
S = list(input())

MOD = 10 ** 9 + 7

LS = len(S)
if K == 0:
    print(1)
    exit()

L = LS + K
DP = [[0] * (LS + 1) for _ in range(L + 10)]
DP[0][0] = 1

for i in range(L + 1):
    for j in range(LS + 1):
        if j < LS:
            DP[i + 1][j] += DP[i][j] * 25
        else:
            DP[i + 1][j] += DP[i][j] * 26

        if j >= 1:
            DP[i + 1][j] += DP[i][j - 1]

        DP[i + 1][j] %= MOD


print(DP[L][LS])

Submission status: Time Limit Exceeded

Solution code:
# F - Strivore
import sys
sys.setrecursionlimit(10**8)
INF = 10**9+7
K = int(input())
S = input()
l = len(S)

def power(x,n):
    global INF
    if n==0:
        return 1
    elif n%2==0:
        return (power(x,n//2)**2)%INF
    else:
        return (x*(power(x,n//2)**2))%INF
    
kakeru = 25
waru = power(26,INF-2)

tmp = power(26,K)
ans = tmp
for i in range(1,K+1):
    tmp = (tmp*kakeru*waru)%INF
    tmp = (tmp*(l-1+i)*power(i,INF-2))%INF
    ans = (ans+tmp)%INF
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

K = int(input())
S = str(input())
mod = 10**9+7
lens = len(S)
length = lens+K

L = 1
pow_dic = {}
pow_dic[0] = 1
for i in range(1, 10**6*2+1):
    L = L*i%mod
    pow_dic[i] = L
ans = 0
for rest in range(K+1):
    lenall = length-rest-1
    nlens = lens-1
    l = pow_dic[lenall]*pow(pow_dic[lenall-nlens], mod-2, mod)%mod
    r = pow_dic[nlens]
    comb = l*pow(r, mod-2, mod)%mod
    ans += pow(25, K-rest, mod)*pow(26, rest, mod)*comb%mod
    ans %= mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

K = ri()
S = rs()

class CombMod:
    def __init__(self, N):
        self.fact = [1]
        self.rfact = [1]
        for i in range(1, N+1):
            self.fact.append(self.fact[i-1]*i % mod)
            self.rfact.append(pow(self.fact[i], mod-2, mod))

    def comb(self, n, k):
        return self.fact[n]*self.rfact[k]*self.rfact[n-k] % mod

N = len(S)
cm = CombMod(K+N)

ans = 0
for i in range(K+1):
	ans += cm.comb(K+N-i-1, N-1) * pow(26, i, mod) * pow(25, K-i, mod)
	ans = ans % mod
print(ans)

Submission status: Time Limit Exceeded

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

P = 10 ** 9 + 7
def mod_prod(a,b):
    return (a % P) * (b % P) % P

def mod_fact(a):
    ret = 1
    for i in range(a):
        ret = ret * (i + 1) % P
    return ret

def mod_pow(a, n):
    ret = 1
    while n > 0:
        if n % 2 == 1:
            ret = ret * a % P
        a = a * a % P
        n = n >> 1
    return ret

def mod_div(a, b):
    b_inv = mod_pow(b, P - 2)
    return a * b_inv % P

def mod_comb(a,b):
    ret = 1
    b = min(b, a - b)
    for i in range(b):
        ret *= a - i
        ret %= P
    ret = mod_div(ret, mod_fact(b))
    return ret

def solve():
    K = int(readline())
    S = readline().rstrip()

    N = len(S)

    ans = 0
    for i in range(K + 1):
        ans += mod_pow(25, i) * mod_comb(i+N-1, i) * mod_pow(26, K-i)
        ans %= P
    print(ans)

solve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)

@mt
def slv(K, S):
    M = 10**9+7
    memo = [0] * (len(S) + 1)
    memo[0] = 1
    for i in range(len(S)+K):
        nm = [0] * (len(S) + 1)
        nm[0] = memo[0] * 25
        nm[0] %= M
        for j in range(1, len(S)):
            nm[j] = memo[j] * 25 + memo[j-1]
            nm[j] %= M
        nm[-1] = memo[-1] * 26 + memo[-2]
        nm[-1] %= M
        memo = nm
    return memo[-1]


def main():
    K = read_int()
    S = read_str()
    print(slv(K, S))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# F - Strivore
import sys
sys.setrecursionlimit(10**8)
INF = 10**9+7
K = int(input())
S = input()
l = len(S)

def power(x,n):
    global INF
    if n==0:
        return 1
    elif n%2==0:
        return (power(x,n//2)**2)%INF
    else:
        return (x*(power(x,n//2)**2))%INF

def comb(n,k):
    global INF
    ans = 1
    if k>n//2:
        k = n-k
    for i in range(k):
        ans = (ans*(n-i)*power(i+1,INF-2))%INF
    return ans

ans = 0
for i in range(K+1):
    ans = (ans+power(26,i)*comb(K-i+l-1,l-1)*power(25,K-i))%INF
print(ans)

Submission status: Time Limit Exceeded

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

dp1 = [0 for i in range(s + 1)]
dp1[0] = 25
dp1[1] = 1
dp2 = [0 for i in range(s + 1)]
# 1moji

# 2moji kara s+k moji
for i in range(2, s + k + 1):
    dp2[0] = dp1[0] * 25
    for j in range(s):
        dp2[j + 1] = dp1[j] + dp1[j + 1] * 25
    dp1 = dp2.copy()
#    print(dp1, (pow(26, s + k, MOD) - sum(dp1[0:-1]) % MOD) % MOD)
print(pow(26, s + k, MOD) - sum(dp1[0:s:]) % MOD)

Submission status: Time Limit Exceeded

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

nagasa = len(s)


ans = pow(26, k, mod)
bunbo = 1
bunshi = 1
for i in range(1, k + 1):
    bunbo *= nagasa - 1 + i
    bunshi *= pow(i, mod - 2, mod)
    bunbo %= mod
    bunshi %= mod
    temp = bunbo * bunshi
    temp %= mod
    temp *= pow(25, i, mod)
    temp %= mod
    temp *= pow(26, k - i, mod)
    temp %= mod
    ans += temp
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===
def fast_pow(num, kata, mod):
    if kata == 0:
        return 1

    res = 1
    while kata > 0:
        if kata & 1 == 1:
            res = res * num % mod
        num = num * num % mod

        kata >>= 1
    return res


def choose(n, r, MOD):
    res = 1
    fac = 1
    for i in range(r):
        res *= n - i
        res %= MOD
        fac *= i + 1
        fac %= MOD
    return res * fast_pow(fac, MOD - 2, MOD) % MOD


def main():
    k = ni()
    s = input()
    l = len(s)

    ans = 0
    for ki in range(k + 1):
        tmpa = fast_pow(25, k - ki, MOD)
        tmpb = fast_pow(26, ki, MOD)
        tmpc = choose(k - ki + l - 1, l - 1, MOD)
        tmpd = (tmpa * tmpb * tmpc) % MOD
        ans += tmpd
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class Combination:
    """
    SIZEが10^6程度以下の二項係数を何回も呼び出したいときに使う
    使い方:
    comb = Combination(SIZE, MOD)
    comb(10, 3) => 120
    """

    def __init__(self, N, MOD=10 ** 9 + 7):
        self.MOD = MOD
        self.fact, self.inv = self._make_factorial_list(N)

    def __call__(self, n, k):
        if k < 0 or k > n:
            return 0
        res = self.fact[n] * self.inv[k] % self.MOD
        res = res * self.inv[n - k] % self.MOD
        return res

    def _make_factorial_list(self, N):
        fact = [1] * (N + 1)
        inv = [1] * (N + 1)
        MOD = self.MOD
        for i in range(1, N + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            inv[i - 1] = (inv[i] * i) % MOD
        return fact, inv


mod = 10 ** 9 + 7
comb = Combination(2 * 10 ** 6 + 10, mod)

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

ans = 0
for i in range(K + 1):
    res = K - i
    right = pow(26, res, mod)
    pos = comb(N - 1 + i, i)
    cnt = pow(25, i, mod)
    tmp = right * pos % mod * cnt % mod
    ans = (ans + tmp) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===
def fast_pow(num, kata, mod):
    if kata == 0:
        return 1

    res = 1
    while kata > 0:
        if kata & 1 == 1:
            res = res * num % mod
        num = num * num % mod

        kata >>= 1
    return res


def choose(n, r, MOD):
    res = 1
    fac = 1
    for i in range(r):
        res *= n - i
        res %= MOD
        fac *= i + 1
        fac %= MOD
    return res * fast_pow(fac, MOD - 2, MOD) % MOD


def main():
    k = ni()
    s = input()
    l = len(s)

    ans = 0
    for ki in range(k + 1):
        tmpa = fast_pow(25, k - ki, MOD)
        tmpb = fast_pow(26, ki, MOD)
        tmpc = choose(k - ki + l - 1, l - 1, MOD)
        tmpd = (tmpa * tmpb * tmpc) % MOD
        ans += tmpd
        ans % MOD
    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
K = int(input())
Str = input()
S = len(Str)

dp = [0]*S 
mod = int(1e9+7)
dp[0] = 1
all_pos = 1

for i in range(S+K):
    all_pos = (all_pos*26)%mod
    next_dp = [0]*S
    next_dp[0] = (dp[0]*25)%mod        

    for j in range(1, S):
        next_dp[j] = ( dp[j-1] + dp[j]*25 ) % mod
    dp = next_dp
t = sum(dp)%mod
print ( (all_pos-t)%mod )

Submission status: Time Limit Exceeded

Solution code:
import copy

def com(n,r,m):
    #a = math.factorial(n)%m
    a = 1
    for i in range(1,n+1):
        a *= i
        a %= m
    A = pow(a,m-2,m)
    
    
    b= copy.copy(A)   
    for i in range(n,r,-1):
        b = (b*i)%m
    
    c = copy.copy(A)
    for i in range(n,n-r,-1):
        c = (c*i)%m
       
    return (a*b*c)%m

def main():
    k = int(input())
    s = input()
    mod = 10**9+7

    ans = 0
    p = 1   #pow(25,i-len(s),mod)
    q = pow(26,k,mod)
    bai = 1
    for i in range(len(s),len(s)+k+1):
        base = p*q   #pow(26,len(s)+k-i,mod)
        #base = pow(25,i-len(s),mod) * pow(26,len(s)+k-i,mod)
        #bai = r
        #bai = com(i-1,len(s)-1,mod)
        #print(i,len(s),base,bai)
        ans += base*bai
        ans %= mod
        p *= 25
        q *= pow(26,mod-2,mod)
        bai = bai*i*pow(i-len(s)+1,mod-2,mod)
    print(ans)
    
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class Combination:
    def __init__(self, n, mod):
        self.mod = mod

        # self.fac[i] ≡ i! (factorial:階乗)
        l = [1]
        num = 1
        for i in range(1, n+1):
            num *= i
            num %= mod
            l.append(num)
        self.fac = l.copy()

        # self.rec[i] ≡ 1 / i! (reciprocal:逆数)
        num = pow(num, mod-2, mod)
        l = [1 for i in range(n+1)]
        l[n] = num
        for i in range(n-1, 0, -1):
            num *= i + 1
            num %= mod
            l[i] = num
        self.rec = l.copy()

    # comb(n, r) ≡ nCr
    def comb(self, n, r):
        return self.fac[n] * self.rec[r] * self.rec[n - r] % self.mod

mod = 10**9 + 7

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

c = Combination(k + n, mod)

pow25 = [1]
pow26 = [1]
for _ in range(k):
    pow25.append(25 * pow25[-1] % mod)
    pow26.append(26 * pow26[-1] % mod)

ans = 0
for i in range(k+1):
    ans += c.comb(n+i-1, i) * pow25[i] * pow26[k-i]
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)

@mt
def slv(K, S):
    M = 10**9+7
    memo = [0] * (len(S) + 1)
    memo[0] = 1
    for i in range(len(S)+K):
        nm = memo[:]
        for j in range(len(S)):
            nm[j] *= 25
            nm[j] %= M
        nm[-1] *= 26
        nm[-1] %= M
        for j in range(1, len(S)+1):
            nm[j] += memo[j-1]
            nm[j] %= M
        memo = nm
    return memo[-1]


def main():
    K = read_int()
    S = read_str()
    print(slv(K, S))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

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

dp = [0]*(n+1)
dp[0] = 25
dp[1] = 1

for i in range(1,n+k):
    pd = [0]*(n+1)
    for j in range(n+1):
        if j == 0:
            pd[j] = (dp[j]*25)%mod
            continue
        if j == n:
            pd[j] = (dp[j]*26+dp[j-1])%mod
            continue
        pd[j] = (dp[j]*25+dp[j-1])%mod
    dp = pd

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from collections import defaultdict
def resolve():
    k = int(input())
    S = input()
    n = len(S)
    dp = {0 : 1}
    for _ in range(n + k):
        ndp = defaultdict(int)
        for key, val in dp.items():
            if key == n:
                ndp[key] += 26 * val
                ndp[key] %= MOD
            else:
                ndp[key + 1] += val
                ndp[key + 1] %= MOD
                ndp[key] += 25 * val
                ndp[key] %= MOD

        dp = ndp
    print(dp[n])
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

def main():
    K = int(input())
    S = deque(input())
    L = len(S)
    """
    dp[i][j] = (i文字目まで埋めた時にSのj文字目までが出現しているような文字列の個数)
    Sの文字はなるべく即座に出現すると考えて重複を防ぐ
    """
    dp = [0] * (L + 1)
    dp[0] = 25
    dp[1] = 1
    for i in range(2, L + K + 1):
        dp2 = [0] * (L + 1)
        dp2[0] = (dp[0] * 25) % mod
        for j in range(1, L):
            dp2[j] = dp[j - 1] + dp[j] * 25
            dp2[j] %= mod
        dp2[L] = dp[L - 1] + dp[L] * 26
        dp2[L] %= mod
        dp = dp2
    print(dp[-1])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

class Combination:
    def __init__(self, size):
        self.size = size + 2
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % MOD
            self.inv[i] = -self.inv[MOD % i] * (MOD // i) % MOD
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % MOD

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % MOD

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % MOD) % MOD

    def nhr(self, n, r):  # 重複組合せ: x_1 + ... + x_n = r
        return self.ncr(n + r - 1, n - 1)

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

comb = Combination(N + K + 100)

ans = 0
for l in range(K + 1):
    r = K - l
    ans += pow(25, l, MOD) * comb.nhr(N, l) * pow(26, r, MOD)
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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

dp = [[0 for j in range(len(S)+1)] for i in range(len(S)+K+1)]
dp[0][0] = 1

for i in range(len(S)+K):
    for j in range(len(S)+1):
        if j == len(S):
            dp[i+1][j] += dp[i][j]*26
            dp[i+1][j] %= MOD
        else:
            dp[i+1][j] += dp[i][j]*25
            dp[i+1][j] %= MOD
            dp[i+1][j+1] += dp[i][j]
            dp[i+1][j+1] %= MOD

print(dp[len(S)+K][len(S)])

Submission status: Time Limit Exceeded

Solution code:
k=int(input())
s=len(input())
mod=10**9+7
fact=[1]*(2*10**6+4+1)
inv=[1]*(2*10**6+4+1)
for i in range(2,2*10**6+4+1):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(2*10**6+4,1,-1):
    inv[i-1]=inv[i]*i%mod
def comb(x,y):return fact[x]*inv[y]%mod*inv[x-y]%mod if x>=y>=0 else 0
print((pow(26,k+s,mod)-sum(25**(k+s-i)*comb(k+s,i) for i in range(s))%mod)%mod)

Submission status: Time Limit Exceeded

Solution code:
class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0



K = int(input())
S = list(input())
s = len(S)

N = K + s

MOD = 10 ** 9 + 7

C = Factorial(N + 10, MOD)

lst26 = [1] * (N + 2)
lst25 = [1] * (N + 2)
for i in range(N + 1):
    lst26[i + 1] = (lst26[i] * 26) % MOD
    lst25[i + 1] = (lst25[i] * 25) % MOD

ans = 0
for x in range(K + 1):
    tmp = ((C.factorial(s - 1 + K - x) * C.ifactorial(s - 1)) % MOD) * C.ifactorial(K - x)
    tmp %= MOD
    tmp = (tmp * lst26[x]) % MOD
    tmp = (tmp * lst25[K - x]) % MOD
    ans = (ans + tmp) % MOD

print (ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

k = int(input())
s = list(input())
mod = 10 ** 9 + 7

nagasa = len(s)

n = nagasa + k
N = 1500 ** 2
Nsq = 1500
fact = np.arange(N, dtype=np.int64).reshape(Nsq, Nsq)
fact[0, 0] = 1
for n in range(1, Nsq):
    fact[:, n] *= fact[:, n - 1]
    fact[:, n] %= mod
for n in range(1, Nsq):
    fact[n] *= fact[n - 1, -1]
    fact[n] %= mod
fact = fact.ravel()
fact_inv = np.arange(1, N + 1, dtype=np.int64)[::-1].reshape(Nsq, Nsq)
fact_inv[0, 0] = pow(int(fact[N - 1]), mod - 2, mod)
for n in range(1, Nsq):
    fact_inv[:, n] *= fact_inv[:, n - 1]
    fact_inv[:, n] %= mod
for n in range(1, Nsq):
    fact_inv[n] *= fact_inv[n - 1, -1]
    fact_inv[n] %= mod
fact_inv = fact_inv.ravel()[::-1]


def comb(n, r):
    if r < 0 or n - r < 0:
        return 0
    res = fact[n]
    res *= fact_inv[n - r]
    res %= mod
    res *= fact_inv[r]
    res %= mod
    return res


ans = 0
for i in range(k + 1):
    temp = 0
    temp += comb(nagasa - 1 + i, nagasa - 1) * pow(25, i, mod)
    temp %= mod
    temp *= pow(26, k - i, mod)
    temp %= mod
    ans += temp
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
l = len(s)
mod = 10**9 + 7
now = [0 for _ in range(l)]
now = [1] + now
for _ in range(n+l):
  last = now
  now = [0 for _ in range(l+1)]
  for i in range(l):
    now[i] += last[i] * 25
    now[i+1] = last[i]
  now[-1] += last[-1] * 26
  for i in range(l+1):
    now[i] %= mod
  #print(now)
print(now[-1])

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class Comb:
    def __init__(self, N):
        F = [1] * (N + 1)
        for i in range(N):
            F[i + 1] = (i + 1) * F[i] % mod

        self.d_inv = {}
        self.d_comb = {}
        self.F = F

    def inv(self, a):
        if a not in self.d_inv:
            self.d_inv[a] = pow(a, mod - 2, mod)
        return self.d_inv[a]

    def comb(self, a, b):
        if (a, b) not in self.d_comb:
            self.d_comb[(a, b)] = (self.F[a] * self.inv(self.F[a - b]) * self.inv(self.F[b])) % mod
            self.d_comb[(a, a - b)] = self.d_comb[(a, b)]
        return self.d_comb[(a, b)] 


def main():
    K = int(input())
    S = input().strip()

    F25 = [1] * (K + 1)
    F26 = [1] * (K + 1)
    for i in range(K):
        F25[i + 1] = (25 * F25[i]) % mod
        F26[i + 1] = (26 * F26[i]) % mod

    comb = Comb(K + len(S) + 1)

    res = 0
    for k in range(K + 1):
        res += ((F25[K - k] * F26[k]) % mod * comb.comb(K - k + len(S) - 1, len(S) - 1)) % mod
        res %= mod
     
    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class Combination:
    def __init__(self, n_max, mod=10**9+7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    # "n 要素" は区別できる n 要素
    # "k グループ" はちょうど k グループ

    def __call__(self, n, r):  # self.C と同じ
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def C(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def P(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[n-r] % self.mod

    def H(self, n, r):
        if (n == 0 and r > 0) or r < 0: return 0
        return self.fac[n+r-1] * self.facinv[r] % self.mod * self.facinv[n-1] % self.mod

    def rising_factorial(self, n, r):  # 上昇階乗冪 n * (n+1) * ... * (n+r-1)
        return self.fac[n+r-1] * self.facinv[n-1] % self.mod

    def stirling_first(self, n, k):  # 第 1 種スターリング数  lru_cache を使うと O(nk)  # n 要素を k 個の巡回列に分割する場合の数
        if n == k: return 1
        if k == 0: return 0
        return (self.stirling_first(n-1, k-1) + (n-1)*self.stirling_first(n-1, k)) % self.mod

    def stirling_second(self, n, k):  # 第 2 種スターリング数 O(k + log(n))  # n 要素を区別のない k グループに分割する場合の数
        if n == k: return 1  # n==k==0 のときのため
        return self.facinv[k] * sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

    def balls_and_boxes_3(self, n, k):  # n 要素を区別のある k グループに分割する場合の数  O(k + log(n))
        return sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

    def bernoulli(self, n):  # ベルヌーイ数  lru_cache を使うと O(n**2 * log(mod))
        if n == 0: return 1
        if n % 2 and n >= 3: return 0  # 高速化
        return (- pow(n+1, self.mod-2, self.mod) * sum(self.C(n+1, k) * self.bernoulli(k) % self.mod for k in range(n))) % self.mod

    def faulhaber(self, k, n):  # べき乗和 0^k + 1^k + ... + (n-1)^k
        # bernoulli に lru_cache を使うと O(k**2 * log(mod))  bernoulli が計算済みなら O(k * log(mod))
        return pow(k+1, self.mod-2, self.mod) * sum(self.C(k+1, j) * self.bernoulli(j) % self.mod * pow(n, k-j+1, self.mod) % self.mod for j in range(k+1)) % self.mod

    def lah(self, n, k):  # n 要素を k 個の空でない順序付き集合に分割する場合の数  O(1)
        return self.C(n-1, k-1) * self.fac[n] % self.mod * self.facinv[k] % self.mod

    def bell(self, n, k):  # n 要素を k グループ以下に分割する場合の数  O(k**2 + k*log(mod))
        return sum(self.stirling_second(n, j) for j in range(1, k+1)) % self.mod

ans = 0
mod = 10**9+7
K = int(input())
S = input()
comb = Combination(2020202)
N = len(S)
for i in range(K+1):
    a = comb(N+K-1-i, N-1)
    a = a * pow(25, K-i, mod) % mod * pow(26, i, mod) % mod
    ans += a
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
def modinv(a, m):
    b, u, v = m, 1, 0
    while(b):
        a, b, u, v = b, a%b, v, u-(a//b)*v
    return u % m

def modpow(a, b, m):
    res = 1
    while(b>0):
        if b&1 == 1:
            res = res * a % m
        b >>= 1
        a = a * a % m
    return res

def modfac(n, m):
    res = [1] * (n+1)
    for i in range(2, n+1):
        res[i] = res[i-1] * i % m
    return res

def modc(n, r, m):
    lst = modfac(n, m)
    return lst[n] * modinv(lst[r], m) * modinv(lst[n-r], m) % m

k = int(input())
s = input()
n = len(s)
mod = 1000000007
ans = 0
for i in range(k+1):
    ans += modc(n-1+i, n-1, mod)*(25**i)*(26**(k-i))
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
K=int(input())
S=input()
n=K+len(S)
#ans=comb(n,min(K,len(S)))
com=1
p=1
q=(26**K)%(10**9+7)
ans=0
for i in range(K+1):
  ans+=(p*q*com)%(10**9+7)#comb(len(S)+i-1,len(S)-1))%(10**9+7)
  p=(p*25)%(10**9+7)
  q=(q*576923081)%(10**9+7)
  com=(com*(len(S)+i))//(i+1)
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
K=int(input())
S=input()
mod=10**9+7
def inv(x):
    return pow(x,mod-2,mod)
N=len(S)
ans=0
tmp1=1
tmp2=1
for i in range(0,K+1):
    ans=ans+(tmp1*tmp2)
    ans%=mod
    tmp1=tmp1*25
    tmp1%=mod
    tmp2=tmp2*(inv(i+1)*(N+K-i))
    tmp2%=mod
    #print(tmp1,tmp2)
print(ans)