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:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7

def perm(n,k):
    if k > n or k < 0: return 0
    return fact[n] * fact_inv[n-k] % MOD

def cmb(n, k):
    if k < 0 or k > n: return 0
    return fact[n] * fact_inv[k] % MOD * fact_inv[n-k] % MOD

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

U = 2 * 10 ** 6 + 100 # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)
K = ir()
S = sr()
length = len(S)
# Sの文字の最後の位置
answer = 0
for i in range(length-1, length+K):
    temp = cmb(i, length-1) * pow(25, i + 1 - length, MOD) % MOD
    temp *= pow(26, length+K-i-1, MOD)
    temp %= MOD
    answer += temp

print(answer%MOD)

Submission status: Time Limit Exceeded

Solution code:
def choose(n, a):
    global mod
    x, y = 1, 1
    for i in range(a):
        x = x * (n - i) % mod
        y = y * (i + 1) % mod
    return x * pow(y, mod - 2, mod) % mod

k = int(input())
n = len(input())
mod = pow(10,9)+7
ans = 0
for i in range(k+1):
    ans += (choose(i+n-1,n-1)*pow(25,i,mod)*pow(26,k-i,mod))
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from numba import njit

P = 10**9+7

nn = 2002002
fa = [1] * (nn+1)
fainv = [1] * (nn+1)
for i in range(nn):
    fa[i+1] = fa[i] * (i+1) % P
fainv[-1] = pow(fa[-1], P-2, P)
for i in range(nn)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % P


def C(a, b): return fa[a] * fainv[b] % P * fainv[a-b] % P if 0 <= b <= a else 0


@njit('i8(i8, i8, i8)', cache=True)
def mod_pow(x, a, MOD):
    ret = 1
    cur = x
    while a:
        if a & 1:
            ret = ret * cur % MOD
        cur = cur * cur % MOD
        a >>= 1
    return ret


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

ans = 0
po = 1
poo = 26 ** K
for i in range(K+1):
    ans += (C(i+M-1, i) * mod_pow(25, i, P) % P * mod_pow(26, K-i, P)) % P
    ans %= P
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class Modulo_Error(Exception):
    pass

class Modulo():
    def __init__(self,a,n):
        self.a=a%n
        self.n=n

    def __str__(self):
        return "{} (mod {})".format(self.a,self.n)

    #+,-
    def __pos__(self):
        return self

    def __neg__(self):
        return  Modulo(-self.a,self.n)

    #等号,不等号
    def __eq__(self,other):
        if isinstance(other,Modulo):
            return (self.a==other.a) and (self.n==other.n)
        elif isinstance(other,int):
            return (self-other).a==0

    def __neq__(self,other):
        return not(self==other)
    
    #加法
    def __add__(self,other):
        if isinstance(other,Modulo):
            if self.n!=other.n:
                raise Modulo_Error("異なる法同士の演算です.")
            return Modulo(self.a+other.a,self.n)
        elif isinstance(other,int):
            return Modulo(self.a+other,self.n)

    def __radd__(self,other):
        if isinstance(other,int):
            return Modulo(self.a+other,self.n)
        
    #減法
    def __sub__(self,other):
        return self+(-other)

    def __rsub__(self,other):
        if isinstance(other,int):
            return -self+other
        
    #乗法
    def __mul__(self,other):
        if isinstance(other,Modulo):
            if self.n!=other.n:
                raise Modulo_Error("異なる法同士の演算です.")
            return Modulo(self.a*other.a,self.n)
        elif isinstance(other,int):
            return Modulo(self.a*other,self.n)
        
    def __rmul__(self,other):
        if isinstance(other,int):
            return Modulo(self.a*other,self.n)
        
    #Modulo逆数
    def Modulo_Inverse(self):
        x0, y0, x1, y1 = 1, 0, 0, 1
        a,b=self.a,self.n
        while b != 0:
            q, a, b = a // b, b, a % b
            x0, x1 = x1, x0 - q * x1
            y0, y1 = y1, y0 - q * y1

        if a!=1:
            raise Modulo_Error("{}の逆数が存在しません".format(self))
        else:
            return Modulo(x0,self.n)
        
    #除法
    def __truediv__(self,other):
        return self*other.Modulo_Inverse()

    #累乗
    def __pow__(self,m):
        u=abs(m)

        r=Modulo(1,self.n)

        while u>0:
            if u%2==1:
                r*=self
            self*=self
            u=u>>1

        if m>=0:
            return r
        else:
            return r.Modulo_Inverse()

#法の合成
def __modulo_composite__(p,q):
    a,n=p.a,p.n
    b,m=q.a,q.n

    d=b-a
    g=GCD(n,m)

    if d%g:
        raise Modulo_Error("{}と{}は両立しません.".format(p,q))

    n//=g
    m//=g
    d//=g

    s=(Modulo(1,m)/Modulo(n,m)).a

    return Modulo(a+(n*g)*d*s,n*m*g)
    

from functools import reduce
def Modulo_Composite(*X):
    return reduce(__modulo_composite__,X)

#素因数分解
def Prime_Factorization(n):
    R=[]
    N=n

    for k in range(2,int(-(-n**0.5//1))+1):
        if N%k==0:
            C=0
            while N%k==0:
                C+=1
                N//=k
            R.append([k,C])

    if N!=1:
        R.append([N,1])
        
    if not R:
        R.append([N,1])

    return R
#----------------------------------------------------------------
K=int(input())
S=input()
M=10**9+7
#----------------------------------------------------------------
f=Modulo(1,M)
Fact=[f]
for i in range(1,len(S)+K+1):
    f*=i
    Fact.append(f)

g=f**(M-2)
Inv=[g]
for j in range(len(S)+K,0,-1):
    g*=j
    Inv=[g]+Inv

def nCr(n,r):
    if 0<=r<=n:
        return Fact[n]/(Fact[r]*Fact[n-r])
    else:
        return Modulo(0,M)

A=len(S)

T=Modulo(0,M)
for i in range(K+1):
    T+=nCr(A+K-1-i,K-i)*(25**(K-i))*(26**i)
print(T.a)

Submission status: Time Limit Exceeded

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

MAXN = L+K+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

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

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline
    K = int(input())
    S = len(input().strip())
    mod = 10 ** 9 + 7
    fact = [1] * (K + S + 1)
    invfact = [1] * (K + S + 1)
    for i in range(K + S):
        fact[i+1] = (fact[i] * (i+1)) % mod
    invfact[-1] = pow(fact[-1], mod-2, mod)
    for i in range(K + S):
        invfact[-2-i] = (invfact[-1-i] * (K + S - i)) % mod
    def nCr(n, r):
        if r == n or r == 0:
            return 1
        r = min(r, n - r)
        return (fact[n] * invfact[n-r] * invfact[r]) % mod
    
    ans = 0
    for i in range(K+1):
        ans += pow(25, i, mod) * nCr(i+S-1, S-1) * pow(26, K-i, mod)
        ans %= mod

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
k=int(input())
s=input()
n=len(s)
c=1
t=1
ans=0
m=10**20
for i in range(k+1):
  ans+=c*t
  if ans>m:ans%=mod
  c*=(n+k-i)*pow(i+1,mod-2,mod)
  if c>m:c%=mod
  t*=25
  if t>m:t%=mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
k=int(input())
s,m,c,a=input(),10**9+7,1,1
for i in range(k):c*=25*(k+len(s)-i)*pow(i+1,m-2,m)%m;c%=m;a+=c
print(a%m)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
k=int(input())
s=input()
n=len(s)
c=1
t=1
ans=0
for i in range(k+1):
  ans+=c*t
  ans%=mod
  c*=(n+k-i)*pow(i+1,mod-2,mod)
  c%=mod
  t*=25
  t%=mod
print(ans)

Submission status: Time Limit Exceeded

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

L26 = [ 1 for i in range(K+1)] # 26^i mod base 
for i in range(K):
  L26[i+1] = (L26[i] * 26) % base

T1 = 1
T2 = 1
ans = 0
for i in range( s, s+K+1):
  T3 = L26[K + s - i]
  #T4 = pow(26, K + s - i, base)
  #print(T3, T4)
  p = (T1 * T2) % base
  p = (p * T3) % base
  ans += p
  ans %= base
  #print(ans, T1, T2, T3)
  T1 *= 25
  T1 %= base
#  T2 = (T2 * i ) // (i+1-s) # T2 = (i, s-1) = (i-1, s-1) * i // (i+1-s)
  T2 *= i
  T2 %= base
  T2 *= pow(i+1-s, base-2, base)
  T2 %= base
  
print(ans % base)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7

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

factorial = [0] * (MAX + 1)
factorial[0] = 1
for i in range(1, MAX + 1):
    factorial[i] = factorial[i-1] * i
    factorial[i] %= MOD


ifactorial = [0] * (MAX + 1)
ifactorial[MAX] = pow(factorial[MAX], MOD - 2, MOD)
for i in range(MAX, 0, -1):
    ifactorial[i - 1] = ifactorial[i] * i
    ifactorial[i - 1] %= MOD

pow25 = [1] * (k + 1)
pow26 = [1] * (k + 1)
for i in range(k):
    pow25[i + 1] = pow25[i] * 25
    pow25[i + 1] %= MOD
    pow26[i + 1] = pow26[i] * 26
    pow26[i + 1] %= MOD


def combination(n, k):
    ret = factorial[n] * ifactorial[k] * ifactorial[n - k]
    return ret % MOD


ans = 0
for i in range(k + 1):
    tmp = combination(i + len(s) - 1, len(s) - 1)
    tmp *= pow25[i]
    tmp %= MOD
    # tmp *= pow(25, i, MOD)
    tmp *= pow26[k - i]
    # tmp *= pow(26, k - i, MOD)
    tmp %= MOD
    ans += tmp
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7

class ModComb:
    def __init__(self, MAX, mod=10 ** 9 + 7):
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, MAX):
            fac.append(fac[i - 1] * i % mod)
            inv.append(mod - inv[mod % i] * (mod // i) % mod)
            finv.append(finv[i - 1] * inv[i] % mod)
        self.fac, self.finv, self.mod = fac, finv, mod

    def nCk(self, n, k):
        if n < k or n < 0 or k < 0:
            return 0
        fac, finv, mod = self.fac, self.finv, self.mod
        return fac[n] * (finv[k] * finv[n - k] % mod) % mod

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

    N = len(S)
    mc = ModComb(N + K + 10)

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

    print(ans)

main()

Submission status: Time Limit Exceeded

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

len_S=len(S)

#逆元を用いたコンビネーション
mod = 10**9+7
def mul_mod(a,b):
  return (a*b) % mod

def fact_inv(a):
  ans = 1
  for i in range(1,a+1):
    ans = (pow(i,mod-2,mod) * ans) % mod
  return ans

fact_list = [1]
for i in range(1,len_S+K):
  fact_list.append(mul_mod(fact_list[-1],i))

fact_list_inv = [1]
for i in range(1,len_S+K):
  fact_list_inv .append((pow(i,mod-2,mod) * fact_list_inv[-1]) % mod)

def comb_inv_mod(a,b):
  return (fact_list[a]*fact_list_inv[b]*fact_list_inv[a-b]) % mod

ans = 0
for i in range(len_S-1,len_S+K): #Snの位置
  #print(i)
  #ans += comb_inv(len_S+K-(len_S+K-i-1)-1,N-1)*pow(25,(K-(len_S+K-i-1)),mod)*pow(26,len_S+K-i-1,mod)
  A = comb_inv_mod(i,len_S-1)*pow(25,i-len_S+1,mod) % mod 
  A = A*pow(26,len_S+K-i-1,mod) % mod
  ans += A
  #print(ans)
  ans = ans % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7

class ModComb:
    def __init__(self, MAX, mod=10 ** 9 + 7):
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, MAX):
            fac.append(fac[i - 1] * i % mod)
            inv.append(mod - inv[mod % i] * (mod // i) % mod)
            finv.append(finv[i - 1] * inv[i] % mod)
        self.fac, self.finv, self.mod = fac, finv, mod

    def nCk(self, n, k):
        if n < k or n < 0 or k < 0:
            return 0
        fac, finv, mod = self.fac, self.finv, self.mod
        return fac[n] * (finv[k] * finv[n - k] % mod) % mod

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

N = len(S)
mc = ModComb(N + K + 10)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7

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

factorial = [0] * (MAX + 1)
factorial[0] = 1
for i in range(1, MAX + 1):
    factorial[i] = factorial[i-1] * i
    factorial[i] %= MOD


ifactorial = [0] * (MAX + 1)
ifactorial[MAX] = pow(factorial[MAX], MOD - 2, MOD)
for i in range(MAX, 0, -1):
    ifactorial[i - 1] = ifactorial[i] * i
    ifactorial[i - 1] %= MOD

pow25 = [1] * (k + 1)
pow26 = [1] * (k + 1)
for i in range(k):
    pow25[i + 1] = pow25[i] * 25
    pow25[i + 1] %= MOD
    pow26[i + 1] = pow26[i] * 26
    pow26[i + 1] %= MOD


def combination(n, k):
    ret = factorial[n] * ifactorial[k] * ifactorial[n - k]
    return ret % MOD


ans = 0
for i in range(k + 1):
    tmp = combination(i + len(s) - 1, len(s) - 1)
    tmp *= pow25[i]
    # tmp *= pow(25, i, MOD)
    tmp *= pow26[k - i]
    # tmp *= pow(26, k - i, MOD)
    tmp %= MOD
    ans += tmp
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class ModCombination():
    def __init__(self, n, mod=998244353):
        self.mod = mod
        self.N = n
        fact = [1, 1] # 元テーブル
        ifact = [1, 1] #逆元テーブル
        inverse = [0, 1] #逆元テーブル計算用テーブル

        for i in range( 2, n + 1 ):
            fact.append( ( fact[-1] * i ) % mod )
            inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
            ifact.append( (ifact[-1] * inverse[-1]) % mod )
        
        self.fact = fact
        self.ifact = ifact
        self.inverse = inverse

    def nCr(self, n, r):
        if r < 0 or r > n:
            return 0
        return self.fact[n] * self.ifact[r] * self.ifact[n-r] % self.mod

    def nPr(self, n, r):
        if r < 0 or r > n:
            return 0
        return self.fact[n] * self.ifact[n-r] % self.mod

def main():
    K = int(input())
    S = input()
    MOD = 10 ** 9 + 7
    N = len(S)
    mc = ModCombination(N+K-1, MOD)

    # 方針
    # SがN文字のとき、
    # S+K文字の文字列からSの文字をどこに配置するか決め、配置を決めたら何パターンあるか計算し、その和をとる
    # 例: S = 'abc', K = 10 のとき, 配置を以下のようにしたとする
    # ***a**b*c****
    # aの前の***にはaを入れない、bの前の**にはbを入れない、cの前の*にはcを入れないようにする
    # 例えば、***ab*b*c**** のように、bの前の**にbを入れてしまうと、
    # ***ab***c**** でパターン数を数えるとき、***ab*b*c****もOKなパターンになるので、最終的に数え上げが重複してしまうため。
    
    # ***a**b*c****
    # この配置のときのパターン数は、
    # [a以外の25文字]^3 x [b以外の25文字]^2 x [c以外の25文字]^1 x [26文字]^4
    # = 26^[最後の文字(c)の後ろの*の数]  x 25^[最後の文字(c)より前にある*の数] 
    # となる。

    # このことから、Sの最後の文字の位置を決めて、それごとにパターン数を数え上げればいいとわかる。

    # Sの最後の文字の後ろの*の数をLとすると、最後の文字より前にある*の数はK-L個
    # 最後の文字以外のN-1文字とK-L個の*の配置パターンは、
    # (N-1+K-L)_C_(N-1) (n_C_r = 組み合わせ)
    # この配置パターンそれぞれに、26^L x 25^(K-L) のパターンがある

    ans = 0
    # Sの最後の文字の後ろの*の数
    for L in range(K+1):
        index_pattern = mc.nCr(N-1+K-L, N-1)
        char_pattern = pow(26, L, MOD) * pow(25, K-L, MOD) % MOD
        ans = (ans + index_pattern * char_pattern) % MOD

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

n = 2*10**6 + 1
factorial = [1]
inverse = [1]
for i in range(1, n+1):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod - 2, mod))

def comb(n, r, mod):
    if n < r or r < 0: return 0
    elif r == 0: return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod

n = len(s)
length = k + n
ans = 0
for i in range(n, length+1):
    temp = 1
    temp *= comb(i-1, n-1, mod)
    temp %= mod
    temp *= pow(25, i-n, mod)
    temp %= mod
    temp *= pow(26, length-i, mod)
    temp %= mod
    ans += temp
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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


factorial = [0] * (MAX + 1)
factorial[0] = 1
for i in range(1, MAX + 1):
    factorial[i] = factorial[i-1] * i
    factorial[i] %= MOD


ifactorial = [0] * (MAX + 1)
ifactorial[MAX] = pow(factorial[MAX], MOD - 2, MOD)
for i in range(MAX, 0, -1):
    ifactorial[i - 1] = ifactorial[i] * i
    ifactorial[i - 1] %= MOD


def combination(n, k):
    ret = factorial[n] * ifactorial[k] * ifactorial[n - k]
    return ret % MOD


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

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

Submission status: Time Limit Exceeded

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

mod=10**9+7

import sys
sys.setrecursionlimit(2147483647)

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
p = mod #割る数
N = 10 ** 7  # 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)

ans=0

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

    #print(end,len(s)+k-end,ans,cmb(end,len(s),mod),pow(25,end-len(s),mod),pow(26,len(s)+k-end,mod))

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
def combination(n, k, mod=10**9+7):
    if n < k:
        return 0
    if n-k < k:
        k = n-k
    comb = 1
    for x in range(n-k+1, n+1):
        comb = (comb * x) % mod
    d = 1
    for x in range(1, k+1):
        d = (d * x) % mod
    comb *= pow(d, mod-2, mod)
    return comb % mod

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

    # 方針
    # SがN文字のとき、
    # S+K文字の文字列からSの文字をどこに配置するか決め、配置を決めたら何パターンあるか計算し、その和をとる
    # 例: S = 'abc', K = 10 のとき, 配置を以下のようにしたとする
    # ***a**b*c****
    # aの前の***にはaを入れない、bの前の**にはbを入れない、cの前の*にはcを入れないようにする
    # 例えば、***ab*b*c**** のように、bの前の**にbを入れてしまうと、
    # ***ab***c**** でパターン数を数えるとき、***ab*b*c****もOKなパターンになるので、最終的に数え上げが重複してしまうため。
    
    # ***a**b*c****
    # この配置のときのパターン数は、
    # [a以外の25文字]^3 x [b以外の25文字]^2 x [c以外の25文字]^1 x [26文字]^4
    # = 26^[最後の文字(c)の後ろの*の数]  x 25^[最後の文字(c)より前にある*の数] 
    # となる。

    # このことから、Sの最後の文字の位置を決めて、それごとにパターン数を数え上げればいいとわかる。

    # Sの最後の文字の後ろの*の数をLとすると、最後の文字より前にある*の数はK-L個
    # 最後の文字以外のN-1文字とK-L個の*の配置パターンは、
    # (N-1+K-L)_C_(N-1) (n_C_r = 組み合わせ)
    # この配置パターンそれぞれに、26^L x 25^(K-L) のパターンがある

    ans = 0
    # Sの最後の文字の後ろの*の数
    for L in range(K+1):
        index_pattern = combination(N-1+K-L, N-1, MOD)
        char_pattern = pow(26, L, MOD) * pow(25, K-L, MOD) % MOD
        ans = (ans + index_pattern * char_pattern) % MOD

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import collections
    K = int(input())
    N = len(input())
    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

    n = N + K
    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)

    d = [0]*(K+1)
    d[0] = 1
    d2 = [0]*(K+1)
    d2[0] = 1

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

        d2[i+1] = d2[i]*25
        d2[i+1] %= mod

    ans = 0
    for i in range(K+1):
        ans += d2[K-i] * d[i] * cmb(N+K-i-1, N-1, mod)
        ans %= mod
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
import collections
K = int(input())
S = input()
N = 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


n = N + K
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)

d = [0]*(K+1)
d[0] = 1
d2 = [0]*(K+1)
d2[0] = 1

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

    d2[i+1] = d2[i]*25
    d2[i+1] %= mod

ans = 0
for i in range(K+1):
    ans += d2[K-i] * d[i] * cmb(N+K-i-1, N-1, mod)
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
readline = sys.stdin.readline

MOD = 10 ** 9 + 7


def main():
    def fact_table(N, MOD):
        inv = np.empty(N, np.int64)
        inv[0] = 0
        inv[1] = 1
        for n in range(2, N):
            q, r = divmod(MOD, n)
            inv[n] = inv[r] * (-q) % MOD
        fact = np.empty(N, np.int64)
        fact[0] = 1
        for n in range(1, N):
            fact[n] = n * fact[n - 1] % MOD
        fact_inv = np.empty(N, np.int64)
        fact_inv[0] = 1
        for n in range(1, N):
            fact_inv[n] = fact_inv[n - 1] * inv[n] % MOD
        return fact, fact_inv, inv

    fac, finv, inv = fact_table(2_000_010, MOD)
    K = int(readline())
    N = len(readline())
    f = np.zeros(K + 1, np.int64)
    f = fac[N - 1:K + N] * finv[N - 1] % MOD * finv[:K + 1] % MOD

    x = 1
    for i in range(1, K + 1):
        x = (x * 25) % MOD
        f[i] = f[i] * x % MOD
    for i in range(1, K + 1):
        f[i] += f[i - 1] * 26
        f[i] %= MOD

    print(f[-1])


import numba
from numba.pycc import CC
i8 = numba.from_dtype(np.int64)
signature = (i8, i8, i8)

main()

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
s = input()
mod = 10**9 + 7
"""
組み合わせ大好きなのにFとけなかったくやしいいいいいいいいいいいいいいいい
"""

def cmb(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

N = 2*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)%mod)
	inv.append((-inv[mod%i]*(mod//i))%mod)
	factinv.append((factinv[-1]*inv[-1])%mod)

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

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
sl = list(input())

n = k + len(sl)
m = len(sl)
# j文字目まで消化したi文字目のパターン
dp = [[0 for _ in range(len(sl)+1)] for _ in range(n+1)]

dp[0][0] = 1
MOD = 10**9 + 7
for i in range(n):
    for j in range(m+1):
        if j == m:
            dp[i+1][j] += dp[i][j] * 26
        else:
            dp[i+1][j] += dp[i][j] * 25
            dp[i+1][j+1] += dp[i][j]
            dp[i + 1][j + 1] %= MOD
        dp[i + 1][j] %= MOD


print(dp[-1][-1])

Submission status: Time Limit Exceeded

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

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

mod=10**9+7

g1=[1,1]#元table
g2=[1,1]#逆元table
inv=[0,1]#逆元table計算用

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

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from functools import lru_cache
sys.setrecursionlimit(1_000_002)

MOD = 1000000007  # type: int

def solve(K: int, S: str):
    '''
    >>> solve(1, 'a')
    51
    '''
    N = len(S)
    mf = ModFactorial(MOD, N+K+1)
    ans = 0    
    for k in range(K+1):
        ans = (ans + mf.combination(k+N-1, k) * pow(25, k, MOD) % MOD * pow(26, K-k, MOD)) % MOD
    return ans

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    print(solve(K, S))

def mod_range(mod, start, stop=None, step=1):    
    if stop == None:
        stop = start
        start = 0
    return map(lambda i: i % mod, range(start, stop, step))

def mod_inv(mod, n):
    '''
    >>> mod_inv(3, 2)
    2
    >>> mod_inv(1000000007, 2)
    500000004
    '''
    return pow(n, mod-2, mod)

def mod_permutation(mod, n, r):
    '''
    >>> mod_permutation(1000000007, 10, 2)
    90
    >>> mod_permutation(7, 10, 2)
    6
    '''
    m = 1
    for i in mod_range(mod, n-r+1, n+1):
        m = (m * i) % mod
    return m

def mod_factorial(mod, n):
    '''
    >>> mod_factorial(1000000007, 10)
    3628800
    >>> mod_factorial(7, 6)
    6
    '''
    return mod_permutation(mod, n, n)

def mod_combination(mod, n, r):
    '''
    >>> mod_combination(1000000007, 10, 2)
    45
    >>> mod_combination(7, 10, 2)
    3
    '''
    return mod_permutation(mod, n, r) * mod_inv(mod, mod_factorial(mod, r)) % mod

class ModFactorial:
    def __init__(self, mod, size=1):
        '''
        >>> ModFactorial(7, 7)
        Traceback (most recent call last):
        ...
        AssertionError
        '''
        assert mod > size
        self._mod = mod
        self._init_factorials(size)

    def _mod_range(self, start, stop=None, step=1):
        return mod_range(self._mod, start, stop, step)
    
    def _mod_inv(self, n):
        return mod_inv(self._mod, n)
    
    def _init_factorials(self, size):
        '''
        >>> mf1 = ModFactorial(1000000007)
        >>> mf2 = ModFactorial(1000000007, 10)
        >>> mf1.factorial(10) == mf2.factorial(10)
        True
        '''
        self._factorials = [1] * size        
        n = 1 # リストの参照は遅いので減らす
        for i, m in enumerate(self._mod_range(1, size), 1):
            n = (n * m) % self._mod
            self._factorials[i] = n
            
    def _append_factorials(self, n):
        for m in map(lambda i: i % self._mod, range(len(self._factorials), n+1)):
            self._factorials.append((self._factorials[-1] * m) % self._mod)

    def factorial(self, n):
        '''
        >>> ModFactorial(1000000007).factorial(10)
        3628800
        >>> ModFactorial(7).factorial(6)
        6
        >>> ModFactorial(7).factorial(7)
        Traceback (most recent call last):
        ...
        AssertionError
        '''
        assert n < self._mod
        if len(self._factorials) <= n:
            self._append_factorials(n)
        return self._factorials[n]

    def factorial_inv(self, n):
        '''
        >>> MOD = 1000000007
        >>> mf = ModFactorial(MOD)
        >>> mf.factorial_inv(10)
        283194722
        >>> mf.factorial_inv(10) * mf.factorial(10) % MOD
        1
        >>> MOD = 7
        >>> mf = ModFactorial(MOD)
        >>> mf.factorial_inv(6)
        6
        >>> mf.factorial_inv(6) * mf.factorial(6) % MOD
        1
        '''
        return self._mod_inv(self.factorial(n))

    def permutation(self, n, r):
        '''
        >>> ModFactorial(1000000007).permutation(10, 2)
        90
        '''
        return self.factorial(n) * self.factorial_inv(n-r) % self._mod

    def combination(self, n, r):
        '''
        >>> ModFactorial(1000000007).combination(10, 2)
        45
        '''
        return self.permutation(n, r) * self.factorial_inv(r) % self._mod

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
K = int(input())
n = len(input())
ans = 0
from math import factorial
for i in range(K+1):
    tmp = pow(26, K-i, MOD)
    tmp = (tmp * pow(25, i, MOD)) % MOD
    tmp = (tmp * (factorial(i+n-1) // (factorial(i) * factorial(n-1))))%MOD  # i+(n-1) C (n-1) = i+(n-1) C i
    ans = (ans + tmp) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
n = len(input())
p = 10**9 + 7
fct, inv = [1], [1]
a, b = 1, 1
for i in range(1, n + k + 1):
    a = (a * i) % p
    b = (b * pow(i, p - 2, p)) % p
    fct.append(a)
    inv.append(b)
ans = 0
for i in range(k + 1):
    c = fct[i + n - 1] * inv[i] * inv[n - 1]
    ans += pow(25, i, p) * pow(26, k - i, p) * c
    ans %= p
print(ans)

Submission status: Time Limit Exceeded

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


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


p = MOD
N = 10 ** 7  # 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)

# Sn の位置をx = l-1,l,..,l+k-1まで全て動かす
# pow(25,x-l-1,MOD)* x-1Cl-1 * pow(26,l+k-1-x,MOD) をかければOK
ans = 0
for x in range(l - 1, l + k):
    ans += pow(25, x - l + 1, MOD) * comb(x, l - 1, MOD) * pow(26, l + k - 1 - x, MOD)
    ans %= MOD
print(ans)
"""
# dp[i][j]:k+l の長さの文字列の中で、長さi で、sのj番目の文字列まじで含む文字列の個数とする
# dp[i][j] = dp[i-1][j-1] + dp[i-1][j] * 25 となる
# これだと10**12でTLEなので、まとめる
# 答えたいのは、dp[k+l][l]で初期化はdp[1][1] = 1 dp[1][0] = 25
# l までいったら遷移の仕方が変わって*26を続けるだけで良いようになる
dp = [[0] * (l + 1) for _ in range(k + l + 1)]
dp[0][0] = 1
for i in range(1, k + l + 1):
    for j in range(l + 1):
        if j == l:
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] * 26
        else:
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] * 25
        dp[i][j] %= MOD
print(dp[k + l][l])
"""

Submission status: Time Limit Exceeded

Solution code:
def main():

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

    mod = pow(10, 9) + 7
    N = len(S)

    g1 = [1, 1]
    g2 = [1, 1]
    inv = [0, 1]

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

    def combi(n, r):
      r = min(r, n-r)
      return g1[n]*g2[r]*g2[n-r]%mod

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

    ans = 0
    for i in range(N-1, N+K):
        ans += combi(i, N-1) * pow25[i-N+1] * pow26[K-i+N-1] % mod
        ans %= mod
    return ans

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