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:
import os
import heapq
import sys
import math
import operator
from collections import defaultdict
from io import BytesIO, IOBase


"""def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)"""

"""def pw(a,b):
    result=1
    while(b>0):
        if(b%2==1): result*=a
        a*=a
        b//=2
    return result"""


def ncr(n, r, p):
    num = den = 1
    for i in range(r):
        num = (num * (n - i)) % p
        den = (den * (i + 1)) % p
    return (num * pow(den,p - 2, p)) % p


def inpt():
    return [int(k) for k in input().split()]


def main():
    k=int(input())
    s=input()
    n=len(s)
    ans=0
    md=10**9+7
    for i in range(k+1):
        ans+=(ncr(n+k-i-1,n-1,md) * (26**i)%md * 25**(k-i)%md )%md
    print(ans)















BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from scipy.special import comb

def input():
    return sys.stdin.readline().strip()
 
def main():
    K = int(input())
    S = input()
 
    mod = 10 ** 9 + 7
    n = len(S)
    ans = 0
 
    for i in range(K+1):
        tmp = pow(25,i,mod)
        tmp *= comb(i+n-1,n-1,exact=True)
        tmp *= pow(26,K-i,mod)
        ans += tmp
        ans %= mod
    print(ans)
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

pow25 = [1] * (N + 1)
fac = [1] * (N + 1)
inv = [1] * (N + 1)
for x in range(1, N + 1):
    fac[x] = fac[x - 1] * x % MOD
    pow25[x] = pow25[x - 1] * 25 % MOD
inv[N] = pow(fac[N], MOD-2, MOD)
for x in range(N - 1, -1, -1):
    inv[x] = inv[x + 1] * (x + 1) % MOD

def binom(n, k):
    return fac[n] * inv[n - k] % MOD * inv[k] % MOD

ans = 0
for k in range(M, N + 1):
    ans += binom(N, k) * pow25[N - k] % MOD
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

K=II()
S=input()
L=len(S)
FACT=FLIST(K+L)
def NCR(n, r):
    res = FACT[n-r]
    res *= FACT[r]
    res %= DVSR
    res = INV(res)
    res *= FACT[n]
    res %= DVSR
    return res

ans = 0
for i in range(K+1):
    v = NCR(L+K-i-1, L-1)
    v *= POW(25, K-i)
    v %= DVSR
    v *= POW(26, i)
    v %= DVSR
    ans += v
    ans %= DVSR

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

K=II()
S=input()
L=len(S)
FACT=FLIST(K+L)
def NCR(n, r):
    res = FACT[n-r]
    res *= FACT[r]
    res %= DVSR
    res = INV(res)
    res *= FACT[n]
    res %= DVSR
    return res

ans = 0
for i in range(K+1):
    v = NCR(L+K-i-1, L-1)
    v *= POW(25, K-i)
    v %= DVSR
    v *= POW(26, i)
    v %= DVSR
    ans += v

print(ans % DVSR)

Submission status: Time Limit Exceeded

Solution code:
import math
def combinations(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
k = int(input())
s = len(input())
ans = 0
for end in range(k+1):#右端の個数は0~k個
    ans += (25**(k-end)*(26**end)*combinations(s+k-end-1,s-1))
print(ans % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
K = int(input())
s = list(input())
S = len(s)
result = 0


for i in range(K + 1):
    p = factorial(S + i - 1) // (factorial(S - 1) * factorial(i))
    q = ((25 ** i) * (26 ** (K - i))) * p
    result += q

print (result % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

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

def cmb(n, r, p):
    assert n < p, 'n is less than modp'
    assert n < max_n, 'n in less than max_n'
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

modp = mod
max_n = k + len(s)+1          # 必要分だけ用意する
fact = [1, 1] + [0]*max_n     # fact[n] = (n! mod modp)
factinv = [1, 1] + [0]*max_n  # factinv[n] = ((n!)^(-1) mod modp)
inv = [0, 1] + [0]*max_n      # factinv 計算用


for i in range(2, max_n + 1):
    fact[i] = (fact[i-1] * i) % modp
    inv[i] = (-inv[modp % i] * (modp // i)) % modp
    factinv[i] = (factinv[i-1] * inv[i]) % modp

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

Submission status: Time Limit Exceeded

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

fac  = [None] * MOD_t_MAX
finv = [None] * MOD_t_MAX
inv  = [None] * MOD_t_MAX
def MOD_COM_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MOD_t_MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD
def MOD_COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

def main():
    k = int(input())
    s = input()
    n = len(s)
    MOD_COM_init()
    ans = 0
    a = 1
    b = pow(26, k, MOD)
    for i in range(k+1):
        ans += a * MOD_COM(i + n-1, n-1) * b % MOD
        a *= 25
        b *= inv[26]
        a %= MOD
        b %= MOD
    print(ans % MOD)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

fac  = [None] * MOD_t_MAX
finv = [None] * MOD_t_MAX
inv  = [None] * MOD_t_MAX
def MOD_COM_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MOD_t_MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD
def MOD_COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

def main():
    k = int(input())
    s = input()
    n = len(s)
    MOD_COM_init()
    ans = 0
    pow_26 = [None]*(k+1)
    pow_25 = [None]*(k+1)
    pow_26[0] = 1
    pow_25[0] = 1
    for i in range(1, k+1):
        pow_26[i] = pow_26[i-1] * 26 % MOD
        pow_25[i] = pow_25[i-1] * 25 % MOD
    for i in range(k+1):
        x, y = i, k-i
        ans += pow_25[x] * MOD_COM(x + n-1, n-1) * pow_26[y] % MOD
    print(ans % MOD)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

l = len(s)

N = k + l + 100
MOD = 10 ** 9 + 7
fact = [0 for _ in range(N)]
invfact = [0 for _ in range(N)]
fact[0] = 1
for i in range(1, N):
    fact[i] = i * fact[i - 1] % MOD

invfact[N - 1] = pow(fact[N - 1], MOD - 2, MOD)

for i in range(N - 2, -1, -1):
    invfact[i] = invfact[i + 1] * (i + 1) % MOD
    
def nCk(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return fact[n] * invfact[k] * invfact[n - k] % MOD

ex_25 = [0 for _ in range(N)]
ex_26 = [0 for _ in range(N)]
ex_25[0] = 1
ex_26[0] = 1
for i in range(1, N):
    ex_25[i] = ex_25[i - 1] * 25 % MOD
    ex_26[i] = ex_26[i - 1] * 26 % MOD

ans = 0
for i in range(k + 1):
    ans += ex_25[i] * ex_26[k - i] * nCk(i + l - 1, i)
    ans %= MOD
    
print(ans)

Submission status: Time Limit Exceeded

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

fct = [1]
invfct = [1]
for i in range(1, K+N+1):
    fct.append(fct[i-1] * i % MOD)
    invfct.append(pow(fct[i], MOD-2, MOD))

def cmb(n, k):
    return fct[n] * invfct[k] * invfct[n-k]

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
input = stdin.readline
def nCr(n,r):
    return fact[n]*(inv[n-r]%M)*(inv[r]%M)
M = 1000000007
k = int(input())
s = len(input().strip())
t = k+s
fact = [1]
p25 = [1]
for i in range(1,t+1):
    fact += [(fact[-1] * i)%M]
    if i<=k:
        p25  += [(p25[-1] * 25) % M]

inv = [1]*(t+1)
inv[t] = pow(fact[t], M-2, M)
for i in range(t-1, -1, -1):
    inv[i] = inv[i+1] * (i+1) % M


res = 0
for i in range(k+1):
    res+=nCr(t,t-i)*p25[i]
    res%=M
print(res)

Submission status: Time Limit Exceeded

Solution code:
M = 10**9 + 7
k,n = int(input()),len(input())
a = t = pow(26,k,M)

for i in range(k):
    t = t*25*(i+n)*pow(26,-1,M)*pow(i+1,-1,M)%M
    a += t

print(a%M)

Submission status: Time Limit Exceeded

Solution code:
K = int(raw_input())
S = len(raw_input())

M = 10**9 + 7

F = [1]
IF = [1]
for i in xrange(1, S + K + 1):
    F.append((F[-1] * i) % M)
    IF.append((IF[-1] * pow(i, M - 2, M)) % M)

def nCr(n, r):
    return (F[n] * IF[r] * IF[n-r]) % M

ans = 0
for i in xrange(K + 1):
    ans = (ans + nCr(i + S - 1, S - 1) * pow(25, i, M) * pow(26, K - i, M)) % M
print ans

Submission status: Time Limit Exceeded

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

M = 10**9 + 7

F = [1]
IF = [1]
for i in range(1, 2 * 10**6 + 1):
    F.append((F[-1] * i) % M)
    IF.append((IF[-1] * pow(i, M - 2, M)) % M)

def nCr(n, r):
    return (F[n] * IF[r] * IF[n-r]) % M

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

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
s = input()
mod = 10**9+7
n = len(s)
fact =[1]*(k+n)
factinv = [1]*(k+n)
inv = [0,1]
 
 
for i in range(2,k+n):
    fact[i] = (fact[i-1] * i) % mod
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv[i] = (factinv[i-1] * inv[i]) % mod

def nCr(n,r):
  r = min(r,n-r)
  return (fact[n] * factinv[r] * factinv[n-r])%mod
ans = 0
for i in range(k+1):
  a = pow(25, i, mod)
  a *= nCr(i+n-1, n-1)
  a *= pow(26,k-i, mod)
  ans += a
  ans %= mod
print (ans)

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
s = input()
mod = 10**9+7
n = len(s)
def nCr(N, R, mod):
	R = min(R, N-R)
	numer = denom = 1
	for i in range(1, R+1):
		numer = numer * (N+1-i) % mod
		denom = denom * i % mod
	return numer * pow(denom, mod-2, mod) % mod


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

Submission status: Time Limit Exceeded

Solution code:
def C(n, r, m):
    num, den = 1, 1
    for i in range(1, r + 1):
        num = num * (n - i + 1) % m
        den = den * i % m
    return (num * pow(den, m - 2, m)) % m

MOD = 10**9 + 7
k = int(input())
s = input()
len_s = len(s)
cnt = 0
for o in range(len_s, len_s + k + 1):
    cnt += C(o - 1, len_s - 1, MOD) * pow(25, o - len_s, MOD) * pow(26, len_s + k - o, MOD) % MOD
print(cnt % MOD)

Submission status: Time Limit Exceeded

Solution code:
import math

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

mod = 10 ** 9 + 7

factorial = [1,1]
inv = [0,1]
finv = [1, 1]
current = 1
for i in range(2, K + len(S) + 1):
    current = (current * i) % mod
    factorial.append(factorial[-1] * i % mod)
    inv.append((- inv[mod % i] * (mod // i)) % mod)
    finv.append(finv[- 1] * inv[-1] % mod)

def combinations_count(n, r):
    r = min(r, n-r)
    return factorial[n] * finv[r] * finv[n - r] % mod

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

answer = 0
lenS = len(S)
for i in range(K + 1):
    n = i + lenS - 1
    r = lenS - 1
    current = combinations_count(n,r) % mod
    current *= pow25[i] % mod
    current *= pow26[K - i] % mod
    answer += current
    answer %= mod

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import math

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

mod = 10 ** 9 + 7

factorial = [1]
current = 1
for i in range(1, K + len(S)):
    current = (current * i)
    factorial.append(current)

def combinations_count(n, r):
    return factorial[n] // (factorial[n - r] * factorial[r])

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

answer = 0
lenS = len(S)
for i in range(K + 1):
    n = i + lenS - 1
    r = lenS - 1
    current = combinations_count(n,r) % mod
    current *= pow25[i] % mod
    current *= pow26[K - i] % mod
    answer += current
    answer %= mod

print(answer)

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7

m25 = [] # 25の階乗をmodで割ったあまりを記録する配列
m26 = [] # 26の階乗
m_n = [1] # 逆元を記録する
a = 1
b = 1

for i in range(k+1):
    m25.append(a)
    a *= 25
    a %= mod

for i in range(k+1):
    m26.append(b)
    b *= 26
    b %= mod

for i in range(2,k+s):
    x = mod % i
    y = mod // i
    c = - m_n[x-1] * y
    c %= mod
    m_n.append(c)

samu = 0
fc = 1
for i in range(k):
    sm = fc
    sm *= m25[i]
    sm *= m26[k-i]
    sm %= mod
    samu += sm

    fc *= (s + i)
    fc %= mod
    fc *= m_n[i]
    fc %= mod

sm = fc
sm *= m25[k]
sm %= mod
samu += sm

samu %= mod
print(samu)

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
s = input()
len_s = len(s)
MOD = 1000000007

pow26_i = pow(26, k, MOD)
inv_26 = pow(26, -1, MOD)
pow25_i = 1
comb_i = 1

a = 0
for i in range(k + 1):  
  a += (comb_i  * pow26_i* pow25_i ) % MOD
  a %= MOD
  
  pow26_i = (pow26_i * inv_26) % MOD
  pow25_i = (pow25_i * 25) % MOD
  comb_i = (comb_i * (len_s + i) * pow(i + 1, -1, MOD)) % MOD


print(a)

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
s = input()
len_s = len(s)
MOD = 1000000007

pow26_i = pow(26, k, MOD)
inv_26 = pow(26, -1, MOD)
pow25_i = 1
comb_i = 1

a = 0
for i in range(k + 1):  
  a += (((comb_i  * pow26_i) % MOD) * pow25_i ) % MOD
  a %= MOD
  
  pow26_i = (pow26_i * inv_26) % MOD
  pow25_i = (pow25_i * 25) % MOD
  comb_i = ((((comb_i * (len_s + i)) % MOD)) * pow(i + 1, -1, MOD)) % MOD


print(a)

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
s = input()
len_s = len(s)
MOD = 1000000007

pow26 = [1] * (k + 1)
pow25_i = 1
comb_i = 1

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

a = 0
for i in range(k + 1):  
  a += (((comb_i  * pow26[k-i]) % MOD) * pow25_i ) % MOD
  a %= MOD

  pow25_i = (pow25_i * 25) % MOD
  comb_i = ((((comb_i * (len_s + i)) % MOD)) * pow(i + 1, -1, MOD)) % MOD


print(a)

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
s = input()
len_s = len(s)
MOD = 1000000007

pow26 = [1] * (k + 1)
pow25 = [1] * (k + 1)
comb = [1] * (k + 1)

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

a = 0
for i in range(k + 1):
  a += (((comb[k-i] * pow26[i]) % MOD) * pow25[k-i]) % MOD
  a %= MOD

print(a)

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
s = input()
len_s = len(s)
MOD = 1000000007

pow26 = [1] * (k + 1)
pow25 = [1] * (k + 1)
comb = [1] * (k + 1)

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

a = 0
for i in range(k + 1):
  a += (comb[k-i] * pow26[i] * pow25[k-i]) % MOD
  a %= MOD

print(a)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs


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

l = k+n + 3
 
a25 = [1]
for i in range(l):
    a25.append((a25[-1] * 25) % MOD)
a26 = [1]
for i in range(l):
    a26.append((a26[-1] * 26) % MOD)

fact, inv = prepare(n+k, MOD)
for i in range(k+1):
    c25 = a25[i]
    f = fact[i+n-1] * inv[i] % MOD * inv[n-1] % MOD
    c25 *= f
    c25 %= MOD

    c26 = a26[k-i]
    ans += (c25 * c26 % MOD)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs


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

fact, inv = prepare(n+k, MOD)
for i in range(k+1):
    c25 = pow(25, i, MOD)
    f = fact[i+n-1] * inv[i] % MOD * inv[n-1] % MOD
    c25 *= f
    c25 %= MOD

    c26 = pow(26, k-i, MOD)
    ans += (c25 * c26 % MOD)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from numba import njit
import numpy as np


MOD = 10**9 + 7

@njit
def fact_table(N, MOD):
    N += 1
    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

@njit
def main(k,n,fact,inv):
    ans = 0
    for i in range(k+1):
        c25 = 1
        for j in range(i):
            c25 *= 25
            c25 %= MOD
        f = fact[i+n-1] * inv[i] % MOD * inv[n-1] % MOD
        c25 *= f
        c25 %= MOD

        c26 = 1
        for h in range(k-i):
            c26 *= 26
            c26 %= MOD
            
        ans += (c25 * c26 % MOD)
        ans %= MOD
    return ans



k = int(input())
s = input()
'''
k = 37564
s = 'whydidyoudesertme'
'''
n = len(s)

fact, fact_inv, inv = fact_table(k+n, MOD)
print(main(k,n,fact,fact_inv))

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs


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

fact, inv = prepare(n+k, MOD)
for i in range(k+1):
    c25 = 25**i
    c25 % MOD
    f = fact[i+n-1] * inv[i] % MOD * inv[n-1] % MOD
    c25 *= f
    c25 %= MOD

    c26 = 26**(k-i)
    c26 % MOD
    ans += (c25 * c26 % MOD)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs


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

fact, inv = prepare(n+k, MOD)
for i in range(k+1):
    c25 = 1
    for j in range(i):
        c25 *= 25
        c25 % MOD
    f = fact[i+n-1] * inv[i] % MOD * inv[n-1] % MOD
    c25 *= f
    c25 %= MOD
    c26 = 1
    for h in range(k-i):
        c26 *= 26
        c26 % MOD
    ans += (c25 * c26 % MOD)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs


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

fact, inv = prepare(10**6, MOD)
for i in range(k+1):
    c25 = 1
    for j in range(i):
        c25 *= 25
        c25 % MOD
    f = fact[i+n-1] * inv[i] % MOD * inv[n-1] % MOD
    c25 *= f
    c25 %= MOD
    c26 = 1
    for h in range(k-i):
        c26 *= 26
        c26 % MOD
    ans += (c25 * c26 % MOD)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs


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

fact, inv = prepare(10**6, MOD)
for i in range(k+1):
    c25 = 1
    for j in range(i):
        c25 *= 25
        c25 % MOD
    f = fact[i+n-1] * inv[i] % MOD * inv[n-1] % MOD
    c25 *= f
    c25 %= MOD
    c26 = 1
    for h in range(k-i):
        c26 *= 26
        c26 % MOD
    ans += (c25 * c26 % MOD)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from scipy.special import comb

mod = 10 ** 9 + 7

K = int(input())
S = str(input())
len_s = len(S)

answer = 0
tmp = 0

inv_25 = pow(25, mod - 2, mod)

for i in range(K + 1):
    if i == 0:
        tmp = pow(25, K-i, mod) * pow(26, i, mod) * comb(K-i+len_s-1, len_s - 1, exact=True)
    else:
        tmp = tmp * inv_25 * 26 * (K - i +1) * pow(K + len_s - i, mod - 2, mod) % mod
    answer += tmp
    answer %= mod
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from scipy.special import comb

mod = 10 ** 9 + 7

K = int(input())
S = str(input())
len_s = len(S)

answer = 0
combination = 0
for i in range(K + 1):
    if i == 0:
        combination = comb(K-i+len_s-1, len_s - 1, exact=True)
    else:
        combination = combination * (K - i +1) * pow(K + len_s - i, mod - 2, mod)
        combination %= mod
    answer += pow(25, K-i, mod) * pow(26, i, mod) * combination
    answer = answer % mod
print(answer)

Submission status: Time Limit Exceeded

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

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

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

Submission status: Time Limit Exceeded

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

ss = len(s)

mod = 10**9 + 7

m25 = []
m26 = []
mfc = []
a = 1
b = 1
c = 1

for i in range(k+1):
    m25.append(a)
    a *= 25
    a %= mod

for i in range(k+1):
    m26.append(b)
    b *= 26
    b %= mod

for i in range(k):
    mfc.append(c)
    c *= ss + i
    c = c // (i+1)
mfc.append(c)

samu = 0
for i in range(k+1):
    sm = mfc[k-i]
    sm %= mod
    sm *= m25[k-i]
    sm *= m26[i]
    sm %= mod
    samu += sm

samu %= mod
print(samu)

Submission status: Time Limit Exceeded

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

ss = len(s)

mod = 10**9 + 7

m25 = []
m26 = []
a = 1
b = 1

for i in range(k+1):
    m25.append(a)
    a *= 25
    a %= mod

for i in range(k+1):
    m26.append(b)
    b *= 26
    b %= mod

samu = 0
for i in range(k+1):
    sm = math.factorial(ss+k-i-1) // (math.factorial(ss-1) * math.factorial(k-i))
    sm %= mod
    sm *= m25[k-i]
    sm *= m26[i]
    sm %= mod
    samu += sm

samu %= mod
print(samu)

Submission status: Time Limit Exceeded

Solution code:
def calc_pow(K, mod):
    pow25 = 1
    pow26 = 1
    li_pow25 = [1]
    li_pow26 = [1]
    for i in range(K + 1):
        pow25 *= 25
        pow25 %= mod
        li_pow25.append(pow25)
        pow26 *= 26
        pow26 %= mod
        li_pow26.append(pow26)
    return li_pow25, li_pow26
    
if __name__ == '__main__':
    K = int(input())
    n = len(input())
    mod = 10**9+7 #出力の制限
    #25 25 a 25 25 25 b 25 25  c  26 26
    cmb = 1
    ans = 0
    pow25, pow26 = calc_pow(K, mod)
    li = []
    for i in range(0, K + 1):
        ans1 = (pow25[i] * cmb) % mod
        ans2 = pow26[K - i]
        cmb = (cmb * (n + i) // (i + 1))
        ans = (ans + (ans1 * ans2) % mod) % mod
        #li.append(pow(25, i, mod))
    
    print(ans)

Submission status: Time Limit Exceeded

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

@author: NEC-PCuser
"""
def calc_pow(K, mod):
    pow25 = 1
    pow26 = 1
    li_pow25 = [1]
    li_pow26 = [1]
    for i in range(K + 1):
        pow25 *= 25
        pow25 %= mod
        li_pow25.append(pow25)
        pow26 *= 26
        pow26 %= mod
        li_pow26.append(pow26)
    return li_pow25, li_pow26
    
if __name__ == '__main__':
    K = int(input())
    n = len(input())
    mod = 10**9+7 #出力の制限
    #25 25 a 25 25 25 b 25 25  c  26 26
    cmb = 1
    ans = 0
    pow25, pow26 = calc_pow(K, mod)
    li = []
    for i in range(0, K + 1):
        ans1 = (pow(25, i, mod) * cmb) % mod
        ans2 = pow(26, K - i, mod)
        cmb = (cmb * (n + i) // (i + 1))
        ans = (ans + (ans1 * ans2) % mod) % mod
        #li.append(pow(25, i, mod))
    
    print(ans)

Submission status: Time Limit Exceeded

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

@author: NEC-PCuser
"""

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/local/bin/python3

'''
Author: andyli
Time: 2020-06-24 21:10:25
'''

mod = 10**9 + 7

m = int(input())
n = len(input())
t = n+m

fac = [0]*(t+1)
ifac = [0]*(t+1)
pw = [0] * (t+1)
fac[0] = 1
for i in range(1, t+1):
    fac[i] = fac[i-1] * i % mod
ifac[t] = pow(fac[t], mod-2, mod)

for i in range(t-1, -1, -1):
    ifac[i] = ifac[i+1] * (i+1) % mod

pw[0] = 1
for i in range(1, t+1):
    pw[i] = pw[i-1] * 25 % mod

def C(n, m):
    return fac[n]*ifac[m]*ifac[n-m]%mod

ans=0
for i in range(n, t+1):
    ans = (ans + pw[t-i] * C(t, i)) % mod

print(ans)

Submission status: Time Limit Exceeded

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

@author: NEC-PCuser
"""

def cmb(n, r):
    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

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

Submission status: Time Limit Exceeded

Solution code:
from scipy.special import comb

mod = 10 ** 9 + 7

K = int(input())
S = str(input())
len_s = len(S)

answer = 0
for i in range(K + 1):
    answer += pow(25, K-i, mod) * pow(26, i, mod) * comb(K-i+len_s-1, len_s - 1, exact=True)
    answer = answer % mod
print(answer)