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:
MOD = 10 ** 9 + 7

fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

def init(n):
    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)

def nPk(n, k):
    return fact[n] * factinv[n - k] % MOD

def nCk(n, k):
    return fact[n] * factinv[n - k] * factinv[k] % MOD

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

init(N + K)
p25 = [1]
p26 = [1]

for k in range(K):
    p25.append(p25[-1] * 25 % MOD)
    p26.append(p26[-1] * 26 % MOD)

ans = 0
for m in range(K + 1):
    n = N + K
    ans += p25[K - m] * p26[m] * nCk(n - 1 - m, N - 1) % MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

def init(n):
    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)

def nPk(n, k):
    return fact[n] * factinv[n - k] % MOD

def nCk(n, k):
    return fact[n] * factinv[n - k] * factinv[k] % MOD

def pow(x, n, mod):
    res = 1
    while n:
        if n % 2:
            res = res * x % mod
        x = x * x % mod
        n //= 2
    return res

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

init(N + K)

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

Submission status: Time Limit Exceeded

Solution code:
import time

MOD = 10 ** 9 + 7

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

fac = [1] * (K + l + 1)
invfac = [1] * (K + l + 1)
for i in range(1, K + l + 1):
	fac[i] = (fac[i - 1] * i) % MOD
	invfac[i] = pow(fac[i], MOD - 2, MOD)

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

ans = 0
for en in range(l - 1, l + K):
	t = (fac[en] * invfac[en - l + 1]) % MOD
	t = (t * invfac[l - 1]) % MOD
	t = (t * p25[en - l + 1]) % MOD
	t = (t * p26[l + K - 1 - en]) % MOD
	ans = (ans + t) % MOD
print(ans)

Submission status: Time Limit Exceeded

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

fac = [1] * (n + k + 2)
for i in range(1, n + k + 1):
    fac[i] = fac[i - 1] * i % mod


def c(n, k):
    return fac[n] * pow(fac[n - k] * fac[k] % mod, mod - 2, mod) % mod


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

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


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

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


ans = 0
for i in range(K + 1):
    cnt = 1
    L = pow25[i] * comb(i + N - 1, i) % mod
    R = pow26[K-i]
    ans += L * R % mod
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def comb_mod(n,r,mod):
    ans = 1
    lis = []
    for i in range(r):
        ans *= n+i
        ans *= pow(i+1,-1,mod)
        ans %= mod
        lis.append(ans)
    return lis
def solve():
    ans = 1
    mod = 10**9+7
    K = int(input())
    S = input()
    s = len(S)
    lis = comb_mod(s,K,mod)
    for k in range(K):
        ans *= 26
        ans += lis[k]*pow(25,k+1,mod)
        ans %= mod
    return ans
print(solve())

Submission status: Time Limit Exceeded

Solution code:
P = 10**9+7

fact = [1 for _ in range(2000001)]
inv = [1 for _ in range(2000001)]
fact_inv = [1 for _ in range(2000001)]

for i in range(2, 2000001):
    fact[i] = (fact[i-1]*i) % P
    inv[i] = P - (inv[P % i] * (P // i)) % P
    fact_inv[i] = (fact_inv[i-1] * inv[i]) % P

K = int(input())
S = input()
N = K + len(S)
ans = 0
for i in range(K+1):
    ans += pow(25, i, P) * (fact[N] * fact_inv[N-i] * fact_inv[i] % P)
    ans = ans % P

print(ans)

Submission status: Time Limit Exceeded

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


mod = 10**9 + 7

b = mod-2
blis = []
c = 0
while b >0:
  if b & 1 == 1:
    blis.append(c)
  c += 1
  b >>= 1

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(c):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res *li[item] %mod
    return res

from collections import deque

kaijou = 1
fact = [1]
for k in range(1, K + S+1):
  kaijou = kaijou * k % mod
  fact.append(kaijou)

fact_k = deque(fact[:K+1])
fact_ks = deque(fact[S-1:])


list26 = deque([1])
list25 = deque([1])
now26 = 26
now25 = 25
for k in range(K):
  list25.append(now25)
  list26.append(now26)
  now25 = now25*25%mod
  now26 = now26*26%mod


ans = 0
for k in range(K+1):
  now = list26.pop()
  now = now * list25.popleft() % mod
  now = now * fact_ks.popleft() % mod
  now = now * modinv(fact_k.popleft()) %mod
  ans += now
  ans %= mod


ans *= modinv(fact[S-1])
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7 #出力の制限
N = 2*10**6+5

def main():
    k = int(input())
    s = input()
    n = len(s)
 
    def cmb1(n, r, mod):
        if ( r<0 or r>n ):
            return 0
        r = min(r, n-r)
        return g1[n] * g2[r] * g2[n-r] % mod
 
    mod = 10**9+7 #出力の制限
    N = 2*10**6+5
    g1 = [1, 1] # 元テーブル
    g2 = [1, 1] #逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル
 
    for i in range( 2, N + 1 ):
        g1.append( ( g1[-1] * i ) % mod )
        inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2.append( (g2[-1] * inverse[-1]) % mod )
 
    def power(a, n, mod):
        bi=str(format(n,"b")) #2進数
        res=1
        for i in range(len(bi)):
            res=(res*res) %mod
            if bi[i]=="1":
                res=(res*a) %mod
        return res
 
    ans = 0
    for i in range(k+1):
        temp = power(25, i, mod)
        temp *= cmb1(i+n-1, n-1, mod)
        temp %= mod
        temp *= power(26, k-i, mod)
        temp %= mod
        ans += temp
    print(ans%mod)
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

s = len(S)
mod = int(1e9+7)

fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, K + s + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

n = 0

for i in range(s, K + s + 1):
    n += (pow(26,(K+s-i),mod)*pow(25,(i-s),mod)*(fact[i-1]*factinv[s-1]*factinv[i-s]))%mod


print(n%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    
    k = int(input())
    s = input()
    n = len(s)
    mod = 10**9+7
    p25 = [0]*(k+1)
    p26 = [0]*(k+1)
    c = [0]*(k+1)

    p25[0], p26[0] = 1, 1
    c[0]= 1
    for i in range(1, k+1):
        p25[i] = p25[i-1]*25
        p25[i] %= mod
        p26[i] = p26[i-1]*26
        p26[i] %= mod
        c[i] = (n+i-1)*c[i-1]
        c[i] *= pow(i, mod-2, mod)
        c[i] %= mod
    p25.reverse()
    c.reverse()
    ans = 0
    for i in range(k+1):
        tmp = p25[i]*p26[i]*c[i]
        tmp %= mod
        ans += tmp
        ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class Combination():
    def __init__(self, n, mod=10**9+7):
        self.mod = mod
        self.fac = [1]*(n+1)
        for i in range(1,n+1):
            self.fac[i] = self.fac[i-1] * i % self.mod
        self.invfac = [1]*(n+1)
        self.invfac[n] = pow(self.fac[n], self.mod - 2, self.mod)
        for i in range(n-1, 0, -1):
            self.invfac[i] = self.invfac[i+1] * (i+1) % self.mod

    def combination(self, n, r):
        return self.fac[n] * self.invfac[r] % self.mod * self.invfac[n-r] % self.mod

    def permutation(self, n, r):
        return self.factorial(n) * self.invfactorial(n-r) % self.mod

    def factorial(self, i):
        return self.fac[i]

    def invfactorial(self, i):
        return self.invfac[i]


def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    
    k = int(input())
    s = input()
    n = len(s)
    mod = 10**9+7
    c = Combination(n+k)
    p25 = [0]*(k+1)
    p26 = [0]*(k+1)
    p25[0], p26[0] = 1, 1
    for i in range(1, k+1):
        p25[i] = p25[i-1]*25
        p25[i] %= mod
        p26[i] = p26[i-1]*26
        p26[i] %= mod

    ans = 0
    for i in range(k+1):
        tmp = c.combination(n+k-i-1, n-1)
        tmp *= p25[k-i]
        tmp %= mod
        tmp *= p26[i]
        tmp %= mod
        ans += tmp
        ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
K=int(input())
L=len(input())
m=10**9+7
from numba import*
@njit(cache=1)
def f():
    max_n=2*10**6
    fac=[1]*(max_n+1)
    inv=[1]*(max_n+1)
    ifac=[1]*(max_n+1)
    for n in range(2,max_n+1):
        fac[n]=(fac[n-1]*n)%m
        inv[n]=m-inv[m%n]*(m//n)%m
        ifac[n]=(ifac[n-1]*inv[n])%m
    return fac,inv,ifac
fac,inv,ifac=f()
def comb(n,k):
    if n<k or n<0 or k<0:
        return 0
    return (fac[n]*ifac[k]*ifac[n-k])%m
d=[1]*(K+1)
d2=[1]*(K+1)
for i in range(K):
    d[i+1]=d[i]*25%m
    d2[i+1]=d2[i]*26%m
print(sum([comb(L+i-1,i)*d[i]*d2[K-i]%m for i in range(K+1)])%m)

Submission status: Time Limit Exceeded

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

FCT = [1]
for i in range(1, K+S+1):
    FCT.append((FCT[-1] * i)%MOD)

def pmu(n, r, mod=MOD):
    return (FCT[n] * pow(FCT[n-r], mod-2, mod)) % mod

def cmb(n, r, mod=MOD):
    return (pmu(n, r) * pow(FCT[r], mod-2, mod)) % mod

def solve():
    ans = 1
    for i in range(S+1, K+S+1):
        ans = (ans*26) % MOD
        add = pow(25, i-S, MOD)
        add = (add * cmb(i-1, i-S)) % MOD
        ans = (ans + add) % MOD
    return ans

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

Submission status: Time Limit Exceeded

Solution code:
M = 10**9+7

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

L = len(S)
#dp = [[-1] * K + L for _ in range(K + L)]
# dp[i][j]  長さi+1の文字列でK[:(j+1)]を含むもの種類
#dp[0][0] = 1

state = [1] + [0] * (L)
# state[i]: K[:i]を含むものの種類
for _ in range(K+L):
  state[L] = (26 * state[L] + state[L-1]) % M
  for i in range(L-1, 0, -1):
    state[i] = (25 * state[i] + state[i-1]) % M
  state[0] = (25 * state[0]) % M
  #print(state)
print(state[L])

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

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

def 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 
    
k = int(input())
S = input()
n = len(S)
MAX = n + k
ans = 0
COMinit()
for i in range(k+1):
    now = pow(26, k-i, MOD)
    now *= pow(25, i, MOD)
    now *= COM(i+n-1, n-1)
    ans += now 

print(ans %MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007
MAX = 1000005
fac = [1,1]
finv = [1,1]
inv = [0,1]
def COMinit():
    for i in range(2,MAX):
        fac.append(( fac[-1] * i) % MOD)
        inv.append((-inv[MOD%i] * (MOD//i)) % MOD)
        finv.append((finv[-1] * inv[-1]) % MOD)

def 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 
    
k = int(input())
S = input()
n = len(S)
ans = 0
COMinit()
for i in range(k+1):
    now = pow(26, k-i) %MOD
    now *= pow(25, i) % MOD
    now *= COM(i+n-1, n-1) % MOD
    ans += now % MOD

print(ans %MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007
class mint:
    def __init__(self,x=0):
        self.x = x % MOD
    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return(
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )

    def __sub__(self, other):
        return(
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    
    def __mul__(self, other):
        return(
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )

    def __truediv__(self, other):
        return(
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2,MOD))
        )

    def __pow__(self, other):
        return(
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )


    __radd__ = __add__

    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )
MAX = MOD
fac = [1,1]
finv = [1,1]
inv = [0,1]
def COMinit():
    for i in range(2,MAX):
        fac.append(( fac[i-1] * i) % MOD)
        inv.append((-inv[MOD%i] * (MOD//i)) % MOD)
        finv.append((finv[-1] * inv[-1]) % MOD)

def 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 

    
k = int(input())
S = input()
n = len(S)
ans = mint(0)


COMinit()
for i in range(k+1):
    now = pow(mint(26), k-i)
    now *= pow(mint(25), i)
    now *= COM(i+n-1, n-1)
    ans += now

print(ans)

Submission status: Time Limit Exceeded

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

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

    
k = int(input())
S = input()
n = len(S)
ans = 0
COMinit()
for i in range(k+1):
    now = pow(26, k-i) %MOD
    now *= pow(25, i) % MOD
    now *= COM(i+n-1, n-1) % MOD
    ans += now

print(ans %MOD)

Submission status: Time Limit Exceeded

Solution code:
import math

MOD = 1000000007
class mint:
    def __init__(self,x=0):
        self.x = x % MOD
    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return(
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )

    def __sub__(self, other):
        return(
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    
    def __mul__(self, other):
        return(
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )

    def __truediv__(self, other):
        return(
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2,MOD))
        )

    def __pow__(self, other):
        return(
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )


    __radd__ = __add__

    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )

    
k = int(input())
S = input()
n = len(S)
ans = mint(0)

def comb(n, r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))

for i in range(k+1):
    now = mint(pow(26, k-i))
    now *= mint(pow(25, i))
    now *= mint(comb(i+n-1, n-1))
    ans += now

print(ans)

Submission status: Time Limit Exceeded

Solution code:
K=int(input())
S=input()
N=len(S)
p=10**9+7
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+K ):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

# ②事前計算した項を掛け合わせ
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



A=0
TF=[1]
TS=[1]
for i in range(K+1):
    TF.append(TF[i]*25 %p)
    TS.append(TS[i]*26 %p)
for i in range(K+1): # Sに含まれる文字を加えるときは、必ず後ろであると考え、S[N-1]の(Sの文字を除いた)位置をiとする
    A=(A+TF[i]*TS[K-i]*cmb(i+N-1,i,p)) %p
print(A)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce
R=10**9+7
K=int(input())
S=input()
N=len(S)

A=0
TF=[1]
TS=[1]
C=[]
for i in range(K+1):
    TF.append(TF[i]*25 %R)
    TS.append(TS[i]*26 %R)
    r = min(i, N-1)
    numer = reduce(mul, range(i+N-1, i+N-1-r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    C.append(numer // denom %R)
for i in range(K+1): # Sに含まれる文字を加えるときは、必ず後ろであると考え、S[N-1]の(Sの文字を除いた)位置をiとする
    A=(A+TF[i]*TS[K-i]*C[i]) %R
print(A)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce
R=10**9+7
def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom
K=int(input())
S=input()
N=len(S)

A=0
TF=[1]
TS=[1]
C=[]
for i in range(K+1):
    TF.append(TF[i]*25 %R)
    TS.append(TS[i]*26 %R)
    C.append(combinations_count(i+N-1, i) %R)
for i in range(K+1): # Sに含まれる文字を加えるときは、必ず後ろであると考え、S[N-1]の(Sの文字を除いた)位置をiとする
    A=(A+TF[i]*TS[K-i]*C[i]) %R
print(A)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom
K=int(input())
S=input()
N=len(S)
R=10**9+7
A=0
TF=[1]
TS=[1]
for i in range(K+1):
    TF.append(TF[i]*25 %R)
    TS.append(TS[i]*26 %R)
for i in range(K+1): # Sに含まれる文字を加えるときは、必ず後ろであると考え、S[N-1]の(Sの文字を除いた)位置をiとする
    A=(A+TF[i]*TS[K-i]*combinations_count(i+N-1, i)) %R
print(A)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

K = int(input())
s = len(input())
MOD = 10**9 + 7

def fft_convolve(f, g):

    Lf, Lg = f.shape[-1], g.shape[-1]
    Lg = g.shape[-1]
    L = Lf + Lg - 1
    fft_len = 1 << L.bit_length()
    fh, fl = f >> 15, f & (1 << 15) - 1
    gh, gl = g >> 15, g & (1 << 15) - 1

    def conv(f, g):
        Ff = np.fft.rfft(f, fft_len)
        Fg = np.fft.rfft(g, fft_len)
        h = np.fft.irfft(Ff * Fg)
        return np.rint(h)[..., :L].astype(np.int64) % MOD

    x = conv(fl, gl)
    z = conv(fh, gh)
    y = conv(fl + fh, gl + gh) - x - z
    return (x + (y << 15) + (z << 30)) % MOD

def coef_of_generating_function(P, Q, N):
    assert Q[0] == 1 and len(Q) == len(P) + 1

    def convolve(f, g):
        return fft_convolve(f, g)

    while N:
        Q1 = np.empty_like(Q)
        Q1[::2] = Q[::2]
        Q1[1::2] = MOD - Q[1::2]
        P = convolve(P, Q1)[N & 1::2]
        Q = convolve(Q, Q1)[::2]
        N >>= 1
    return P[0]

den = np.array([1, -26])
for _ in range(s):
  den = fft_convolve(den, np.array([1, -25]))

num = np.zeros_like(den)[:-1]
num[0] = 1

print(coef_of_generating_function(num, den, K))

Submission status: Time Limit Exceeded

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

K = int(readline())
S = readline().rstrip()
S = len(S)
N = K + S

DIV = 10 ** 9 + 7

# K = 3, S = 5のとき
# ..X.X.X.
# Xが取る3か所を選んだ上で、
# 最も右のXよりも右のマス：各26通り
# 最も右のXを含む、それより左のマス：Xのマスは1通り、それ以外は各25通り
# 最も右のXが
# ..X.....　の状態から、
# .......X  
# の状態について、場合の数を求める

ans = 0
ncr = 1
div = 1
mul = S - 1
for xpos in range(S, N + 1):
  # xpos箇所からK箇所を選ぶ場合の数
  # 一番右に1個固定した状態で、残りのxpos - 1か所からS - 1個を選ぶ
  pat = ncr
  mul += 1
  # nCrのnを一つずつ増やしていく。割り算の剰余は逆元との積を取る
  ncr = (ncr * mul * pow(div, -1, DIV)) % DIV
  div += 1
  # その場合の数に対して、X以外の文字の選び方は25 ** (X - S)通りある
  pat *= pow(25, xpos - S, DIV)
  pat %= DIV
  
  # 残りのマスに対しては26通りずつ選べる
#  print("26 for ",N - xpos,"boxes")
  pat *= pow(26, N - xpos, DIV)
  pat %= DIV
#  print("xpos",xpos,"pat",pat)
  
  ans += pat
  ans %= DIV

print(ans)

Submission status: Time Limit Exceeded

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

K = int(readline())
S = readline().rstrip()
S = len(S)
N = K + S

DIV = 10 ** 9 + 7
n = (10 ** 6) * 2
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

# K = 3, S = 5のとき
# ..X.X.X.
# Xが取る3か所を選んだ上で、
# 最も右のXよりも右のマス：各26通り
# 最も右のXを含む、それより左のマス：Xのマスは1通り、それ以外は各25通り
# 最も右のXが
# ..X.....　の状態から、
# .......X  
# の状態について、場合の数を求める

ans = 0
for xpos in range(S, N + 1):
  # xpos箇所からK箇所を選ぶ場合の数
  # 一番右に1個固定した状態で、残りのxpos - 1か所からS - 1個を選ぶ
  pat = nCr(xpos - 1, S - 1, DIV)
  # その場合の数に対して、X以外の文字の選び方は25 ** (X - S)通りある
  pat *= pow(25, xpos - S, DIV)
  pat %= DIV
  
  # 残りのマスに対しては26通りずつ選べる
  pat *= pow(26, N - xpos, DIV)
  pat %= DIV
  
  ans += pat
  ans %= DIV

print(ans)

Submission status: Time Limit Exceeded

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

from scipy.special import comb

K = int(readline())
S = readline().rstrip()
S = len(S)
N = K + S

DIV = 10 ** 9 + 7

# K = 3, S = 5のとき
# ..X.X.X.
# Xが取る3か所を選んだ上で、
# 最も右のXよりも右のマス：各26通り
# 最も右のXを含む、それより左のマス：Xのマスは1通り、それ以外は各25通り
# 最も右のXが
# ..X.....　の状態から、
# .......X  
# の状態について、場合の数を求める

ans = 0
for xpos in range(S, N + 1):
  # xpos箇所からK箇所を選ぶ場合の数
  # 一番右に1個固定した状態で、残りのxpos - 1か所からS - 1個を選ぶ
  pat = comb(xpos - 1, S - 1, exact=True)
#  print("xpos",xpos,"ncr",ncr)
#  print(S,"from",xpos,"pat",pat)
  # その場合の数に対して、X以外の文字の選び方は25 ** (X - S)通りある
#  print("25 for",xpos - S,"boxes")
  pat *= pow(25, xpos - S, DIV)
  pat %= DIV
  
  # 残りのマスに対しては26通りずつ選べる
#  print("26 for ",N - xpos,"boxes")
  pat *= pow(26, N - xpos, DIV)
  pat %= DIV
#  print("xpos",xpos,"pat",pat)
  
  ans += pat
  ans %= DIV

print(ans)

Submission status: Time Limit Exceeded

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

K = int(readline())
S = readline().rstrip()
S = len(S)
N = K + S

DIV = 10 ** 9 + 7

# K = 3, S = 5のとき
# ..X.X.X.
# Xが取る3か所を選んだ上で、
# 最も右のXよりも右のマス：各26通り
# 最も右のXを含む、それより左のマス：Xのマスは1通り、それ以外は各25通り
# 最も右のXが
# ..X.....　の状態から、
# .......X  
# の状態について、場合の数を求める

ans = 0
ncr = 1
div = 1
mul = S - 1
for xpos in range(S, N + 1):
  # xpos箇所からK箇所を選ぶ場合の数
  # 一番右に1個固定した状態で、残りのxpos - 1か所からS - 1個を選ぶ
  pat = ncr
#  print("xpos",xpos,"ncr",ncr)
  mul += 1
  ncr = ncr * mul // div
  div += 1
#  print(S,"from",xpos,"pat",pat)
  # その場合の数に対して、X以外の文字の選び方は25 ** (X - S)通りある
#  print("25 for",xpos - S,"boxes")
  pat *= pow(25, xpos - S, DIV)
  pat %= DIV
  
  # 残りのマスに対しては26通りずつ選べる
#  print("26 for ",N - xpos,"boxes")
  pat *= pow(26, N - xpos, DIV)
  pat %= DIV
#  print("xpos",xpos,"pat",pat)
  
  ans += pat
  ans %= DIV

print(ans)

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
    ar26=[1]
    ar25=[1]
    a=1
    b=1
    for i in range(k):
        a*=25
        a%=md
        b*=26
        b%=md
        ar26.append(b)
        ar25.append(a)

    for i in range(k+1):
        ans+=(ncr(n+k-i-1,n-1,md)*ar26[i]*ar25[k-i])
        ans%=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 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) * (pow(26, i, md)) % md * pow(25, k - i, md)) % md
        ans %= 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()