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:
K = int(input())
N = len(input())

mod = 10 ** 9 + 7
comb_i = pow(26, K, mod)
ans = comb_i
for i in range(1, K + 1):
  comb_i = (comb_i * (N - 1 + i) * pow(i, -1, mod)) % mod
  comb_i = (comb_i * 25 * pow(26, -1, mod)) % mod
  ans = (ans + comb_i) % mod
  
print(ans)

Submission status: Time Limit Exceeded

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

mod = 10 ** 9 + 7
comb_i = pow(26, K, mod)
ans = comb_i
for i in range(1, K + 1):
  comb_i = (comb_i * (N - 1 + i)) % mod
  comb_i = (comb_i * 25) % mod
  comb_i = (comb_i * pow(i, -1, mod)) % mod
  comb_i = (comb_i * pow(26, -1, mod)) % mod
  ans = (ans + comb_i) % mod
  
print(ans)

Submission status: Time Limit Exceeded

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

mod = 10 ** 9 + 7
comb_i = pow(26, K, mod)
ans = comb_i
for i in range(1, K + 1):
  comb_i = ((comb_i * (N - 1 + i) * 25) * pow(i, -1, mod) * pow(26, -1, mod)) % mod
  ans += comb_i
  
print(ans % mod)

Submission status: Time Limit Exceeded

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

mod = 10 ** 9 + 7
comb_i = 26 ** K
ans = comb_i
for i in range(1, K + 1):
  comb_i *= (N + i - 1) * 25
  comb_i //= i * 26
  ans += comb_i
  
print(ans % mod)

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


def main():
    k = int(input())
    s = input()

    len_s = len(s)

    ans = 0
    for i in range(k + 1):
        n = 26 ** (k - i)
        n *= 25 ** i
        n *= combinations_count(i + len_s - 1, len_s - 1)
        ans += n

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
k=int(input())
s=input()
l=len(s)
fact=[1]
for i in range(1,k+l+1):
  fact.append((fact[-1]*i)%mod)
revfact=[]
for i in range(k+l+1):
  revfact.append(pow(fact[i],mod-2,mod))
pow1=[1]
pow2=[1]
for i in range(1,k+l+1):
  pow1.append((pow1[-1]*25)%mod)
  pow2.append((pow2[-1]*26)%mod)
ans=0
for i in range(k+l):
  coef1=(pow1[k-i]*pow2[i])%mod
  if i<=k:
    coef2=(fact[k+l-1-i]*revfact[l-1]*revfact[k-i])%mod
  else:
    coef2=0
  ans+=coef1*coef2
  ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
k=int(input())
s=input()
l=len(s)
fact=[1] #0!～(|S|+k)!の前計算を行う
for i in range(1,k+l+1):
 fact.append((fact[-1]*i)%mod)
revfact=[]
for i in range(k+l+1): #0!～(|S|+k)!の逆数の前計算を行う
 revfact.append(pow(fact[i],mod-2,mod))
pow1=[1]
pow2=[1]
for i in range(1,k+l+1): #25^Kと26^Kの前計算を行う
 pow1.append((pow1[-1]*25)%mod)
 pow2.append((pow2[-1]*26)%mod)
ans=0
for i in range(k+l): #Sの最後の文字を置く場所を|S|+Kマスの中からすべて試す
 coef1=(pow1[k-i]*pow2[i])%mod
 if i<=k:
   coef2=(fact[k+l-1-i]*revfact[l-1]*revfact[k-i])%mod
 else:
   coef2=0
 ans+=coef1*coef2
 ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = int(10e9+7)
maxn = int(10e6+10)

def mod(x, m = MOD):
    tmp = x%m 
    if(tmp < 0): tmp += m 
    return tmp

def fpow(x, y, m = MOD):
    res = 1
    while(y):
        if y%2:
            res =  mod(res*x)
        y>>=1
        x = mod(x*x)
    return res

fat = [1]
ifat = [1]
power25 = [1]

for i in range(1,maxn):
    fat.append(mod(fat[i-1]*i))
    power25.append(mod(25*power25[i-1]))
    ifat.append(fpow(fat[i], MOD - 2))

def comb(n, k):
    return mod(mod(fat[n] * ifat[n-k]) * ifat[k])

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

ans = fpow(26,n)

for m in range(0,len(s)):
    tmp = mod(power25[n-m]*comb(n,m))
    ans = mod(ans-tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = int(10e9+7)
maxn = int(10e6+10)

fat = [1]
power25 = [1]

for i in range(1,maxn):
    fat.append((fat[i-1]*i)%MOD)
    power25.append((25*power25[i-1])%MOD)

def comb(n, k):
    return fat[n] // (fat[k] * fat[n-k])

def fpow(x, y):
    res = 1
    while(y):
        if y%2:
            res =  (res*x)%MOD 
        y>>=1
        x = (x*x)%MOD
    return res

def sub(x, y):
    x = (x-y)%MOD
    if(x < 0): x+=MOD
    return x

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

n = len(s) + k 

ans = fpow(26,n)

for m in range(0,len(s)):
    tmp = power25[n-m]*comb(n,m)
    ans = sub(ans,tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# F - Strivore

K = int(input())
S = list(str(input()))
N = len(S)
MOD = 10**9+7

fac = [1, 1]
inv = [0, 1]
finv = [1, 1]
pow25 = [1, 25]
pow26 = [1, 26]

for i in range(2, N+K+1):
    fac.append(fac[-1] * i % MOD)
    inv.append(MOD - inv[MOD%i] * (MOD//i) % MOD)
    finv.append(finv[-1] * inv[-1] % MOD)
    if i <= K+1:
        pow25.append(pow(25, i, MOD))
        pow26.append(pow(26, i, MOD))

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


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

Submission status: Time Limit Exceeded

Solution code:
import sys

def input():
    return sys.stdin.readline().strip()

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

    mod = 10 ** 9 + 7
    n = len(S)
    ans = 0

    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

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def input():
    return sys.stdin.readline().strip()

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

    mod = 10 ** 9 + 7
    n = len(S)
    ans = 0

    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):
        return (fact[n] * factinv[r] * factinv[n-r]) % mod

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# F - Strivore

K = int(input())
S = list(str(input()))
N = len(S)
MOD = 10**9+7

fac = [1, 1]
inv = [0, 1]
finv = [1, 1]

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys

def input():
    return sys.stdin.readline().strip()

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

    mod = 10 ** 9 + 7
    n = len(S)
    ans = 0

    fact =[1]*(K+n)
    factinv = [1]*(K+n)


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

    def nCr(n,r):
        return (fact[n] * factinv[r] * factinv[n-r]) % mod

    for i in range(K+1):
        #ans += ((25 ** i * nCr(i+n-1,n-1)) * (26 ** (K - i))) % mod
        ans += ((25 ** i * fact[i+n-1] * factinv[n-1] * factinv[i] ) * (26 ** (K - i))) % mod
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def input():
    return sys.stdin.readline().strip()

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

    mod = 10 ** 9 + 7
    n = len(S)
    ans = 0

    fact =[1]*(K+n)
    factinv = [1]*(K+n)


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

    def nCr(n,r):
        return (fact[n] * factinv[r] * factinv[n-r]) % mod

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def input():
    return sys.stdin.readline().strip()

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

    mod = 10 ** 9 + 7
    n = len(S)
    ans = 0

    fact =[1,1]
    factinv = [1,1]


    for i in range(2,K+n):
        fact.append((fact[-1] * i) % mod)
        factinv.append(pow(fact[-1],mod-2,mod))

    def nCr(n,r):
        return (fact[n] * factinv[r] * factinv[n-r]) % mod

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def invmod(a):
  return pow(a,MOD-2,MOD)
fact_dic={0:1}
fact_inv_dic={0:1}
fact_mod=1
for i in range(1,K+len_S+1):
  fact_mod=(fact_mod*i)%MOD
  fact_dic[i]=fact_mod
  fact_inv_dic[i]=invmod(fact_mod)
def comb_mod_table(n,r):
  if 0<=r<=n:
    return fact_dic[n]*fact_inv_dic[r]*fact_inv_dic[n-r]
  else:
    return 0
  
answer=0
for i in range(K+1):
  answer+=comb_mod_table(K+len_S-i-1,len_S-1)*pow(25,K-i,MOD)*pow(26,i,MOD)
  answer%=MOD
  
print(answer)

Submission status: Time Limit Exceeded

Solution code:
def prepare(n, MOD):

    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    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()
length = len(s)
MOD = 10**9 + 7

fact, inv = prepare(k + length, MOD)

ans = 0

for i in range(length, length + k + 1):
    coef = fact[i - 1] * inv[i - length] * inv[length - 1] % MOD
    ans += coef * pow(25, i - length, MOD) * pow(26, length + k - i, MOD) % MOD

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
def prepare(n, MOD):

    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    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()
length = len(s)
MOD = 10**9 + 7

fact, inv = prepare(k + length, MOD)

ans = 0

for i in range(length, length + k + 1):
    coef = fact[i - 1] * inv[i - length] * inv[length - 1]
    ans += coef * pow(25, i - length, MOD) * pow(26, length + k - i, MOD) % MOD

print(ans % MOD)

Submission status: Time Limit Exceeded

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

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

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

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

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

i25, i26 = [1], [1]
for _ in range(k+1):
    i25.append(i25[-1] * 25 % mod)
    i26.append(i26[-1] * 26 % mod)

n = len(s)
ans = 0
for i in range(k+1):
    ans += i25[i] * i26[k-i] * nCr(i+n-1, n-1, mod)
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

def invmod(a):
  return pow(a,MOD-2,MOD)
fact_dic={0:1}
fact_inv_dic={0:1}
fact_mod=1
for i in range(1,K+len_S+1):
  fact_mod=(fact_mod*i)%MOD
  fact_dic[i]=fact_mod
  fact_inv_dic[i]=invmod(fact_mod)
def comb_mod_table(n,r):
  if 0<=r<=n:
    return fact_dic[n]*fact_inv_dic[r]*fact_inv_dic[n-r]
  else:
    return 0
  
answer=pow(26,K+len_S,MOD)
for i in range(len_S):
  answer-=comb_mod_table(K+len_S,i)*pow(25,K+len_S-i,MOD)
  answer%=MOD
  
print(answer)

Submission status: Time Limit Exceeded

Solution code:

from collections import defaultdict

# ----------

INF = float("inf")
MOD = 10 ** 9 + 7
# ----------

def combination(a, b):
    if b > a - b:
        return combination(a, a - b)
    return fact[a] * ifact[b] * ifact[a-b]


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

# 階乗を前処理
fact = defaultdict(int)
fact[0] = 1
for i in range(1, N+K+1):
    fact[i] = fact[i-1] * i
    fact[i] %= MOD
# 階乗の逆元を前処理
ifact = defaultdict(int)
ifact[N+K] = pow(fact[N+K], MOD-2, MOD)
for i in reversed(range(1, N+K+1)):
    ifact[i-1] = ifact[i] * i
    ifact[i-1] %= MOD

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce


def ccnt(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()
length = len(s)
MOD = 10**9 + 7

ans = 0

for i in range(length, length + k + 1):
    ans += ccnt(i - 1, length - 1) * pow(25, i - length, MOD) * pow(26, length + k - i, MOD) % MOD

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys

K = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip('\n')

# ## COMBINATION (MOD) ###
N_MAX = 2*10**6  # 問題サイズに合わせて変えておく
MOD = 10**9 + 7

fac = [1, 1]  # 元テーブル
facinv = [1, 1]  # 逆元テーブル
inv = [0, 1]  # 逆元テーブル計算用テーブル

for i in range(2, N_MAX + 1):
    fac.append((fac[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    facinv.append((facinv[-1] * inv[-1]) % MOD)


def cmb(n, r):
    if (r < 0 or r > n):
        return 0
    # r = min(r, n-r)
    return fac[n] * facinv[r] * facinv[n - r] % MOD

# K 文字追加
ans = 0

ln = len(S)

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

    # pre
    p = i - 1
    p1 = cmb(p, ln - 1)
    p2 = pow(25, p - (ln - 1), MOD)

    # suf
    s = (ln + K) - i
    s2 = pow(26, s, MOD)

    ans += p1*p2*s2 % MOD
    ans %= MOD

    # print(p, p1,p2, s, s2)

print(ans)

Submission status: Time Limit Exceeded

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

MOD = 10**9+7

fac = [1, 1]     # 元テーブル

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

def modcmb(n, r, mod):
    if n < 0 or r < 0:
        return 0
    if r > n:
        return 0

    return fac[n] * pow(fac[r], -1, MOD) * pow(fac[n-r], -1, MOD) % mod


def main():
    K = int(readline())
    S = readline().strip()
    N = len(S)

    prepare(N + K + 10, MOD)

    inv26 = pow(26, -1, MOD)
    exp = pow(26, K, MOD)
    ans = 0
    for i in range(K+1):
        tmp = exp * modcmb(N-1+i, i, MOD)
        tmp %= MOD
        ans += tmp
        ans %= MOD

        exp *= 25 * inv26
        exp %= MOD

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

MOD = 10**9+7

fac = [1, 1]     # 元テーブル

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

def modcmb(n, r, mod):
    if n < 0 or r < 0:
        return 0
    if r > n:
        return 0

    return fac[n] * pow(fac[r], -1, MOD) * pow(fac[n-r], -1, MOD) % mod


def main():
    K = int(readline())
    S = readline().strip()
    N = len(S)

    prepare(N + K + 10, MOD)

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

MOD = 10**9+7

fac = [1, 1]     # 元テーブル

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

def modcmb(n, r, mod):
    if n < 0 or r < 0:
        return 0
    if r > n:
        return 0

    return fac[n] * pow(fac[r], MOD-2, MOD) * pow(fac[n-r], MOD-2, MOD) % mod


def main():
    K = int(readline())
    S = readline().strip()
    N = len(S)

    prepare(N + K + 10, MOD)

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

MOD = 10**9+7

fac = [1, 1]     # 元テーブル
f_inv = [1, 1]   # 逆元テーブル
inv = [0, 1]     # 逆元テーブル計算用テーブル

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

def modcmb(n, r, mod):
    if n < 0 or r < 0:
        return 0
    if r > n:
        return 0

    return fac[n] * f_inv[r] * f_inv[n-r] % mod


def main():
    K = int(readline())
    S = readline().strip()
    N = len(S)

    prepare(N + K + 10, MOD)

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

length = len(s)
MOD = 10**9 + 7

dp = [[0] * (k + 1) for _ in range(2)]
dp[0][0] = pow(26, k, MOD)
dp[1][0] = pow(26, k, MOD)

div = pow(26, -1, MOD)

for i in range(1, k + 1):
    dp[0][i] = dp[0][i - 1] * 25 * div * (length + i - 1) * pow(i, -1, MOD) % MOD
    dp[1][i] = (dp[1][i - 1] + dp[0][i]) % MOD

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

Submission status: Time Limit Exceeded

Solution code:
from numba import njit, i8, void
import numpy as np

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


@njit(i8(i8, i8, i8), cache=True)
def pow(n, k, mod):
    l, now = [1]*64, 1
    l[0] = n
    for i in range(1, 64):
        l[i] = l[i-1]*l[i-1] % mod
    for i in range(64):
        if k & 1:
            now = now*l[i] % mod
        k >>= 1
    return now


@njit(void(i8, i8, i8), cache=True)
def num_calc(n, k, mod):
    fact = np.ones(n+k+1, dtype=np.int64)
    for i in range(2, n+k+1):
        fact[i] = fact[i-1]*i % mod

    power = np.ones(k+1, dtype=np.int64)
    power[0] = fact[n+k]
    for i in range(1, k+1):
        power[i] = power[i-1]*25 % mod

    fact = fact[n+k:n-1:-1]*fact[:k+1] % mod
    ans = 0
    for i in range(k+1):
        ans = (ans+pow(fact[i], mod-2, mod)*power[i]) % mod
    print(ans)


num_calc(n, k, mod)

Submission status: Time Limit Exceeded

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

MOD = 10**9 + 7

fact = [1] * 2200000
invfact = [1] * 2200000

for i in range(1, 2200000):
  fact[i] = fact[i-1] * i % MOD

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

for i in range(2200000-1, 0, -1):
  invfact[i-1] = invfact[i] * i % MOD

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

ans = 0

for l in range(n, n+k+1):
  ans += pow(25, l-n, MOD) * nCk(l-1,n-1) * pow(26, n+k-l, MOD) % MOD
  ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from scipy.special import comb

k = int(input())
s = input()
slen = len(s)
md = 10 ** 9 + 7

ans = 0
dict = {}
for i in range(k+1):
    now = pow(26, k-i, md) * pow(25, i, md)
    key = (i+slen-1, slen-1)
    ret = dict.get(key)
    if not ret:
        ret = comb(key[0], key[1], exact=True)
        dict[key] = ret
    now *= ret
    ans = (ans + now) % md
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 = []
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:
from scipy.special import comb

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

def mod(p):
    return p % (10 ** 9 + 7)

ans = 0
for i in range(k+1):
    ans += mod(mod(26 ** (k - i)) * mod(25 ** i) * comb(i+slen-1, slen-1, exact=True))
print(mod(ans))

Submission status: Time Limit Exceeded

Solution code:
from scipy.special import comb

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

ans = 0
for i in range(k+1):
    ans += 26 ** (k - i) * 25 ** i * comb(i+slen-1, slen-1, exact=True)
print(ans % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
from numba import njit, i8
import numpy as np

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

    @njit(i8[:](i8, i8), cache=True)
    def num_calc(n, mod):
        fact = np.ones(n+1, dtype=np.int64)
        for i in range(2, n+1):
            fact[i] = fact[i-1]*i % mod
        return fact

    @njit(i8[:](i8, i8), cache=True)
    def num_calc2(k, mod):
        power = np.ones(k+1, dtype=np.int64)
        for i in range(1, k+1):
            power[i] = power[i-1]*25 % mod
        return power

    fact = num_calc(n+k, mod).tolist()
    power = num_calc2(k, mod).tolist()
    nk = fact[n+k]

    print(sum([pow(fact[n+k-i]*fact[i] % mod, mod-2, mod)
               * nk*power[i] % mod for i in range(k+1)]) % mod)


main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 15

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

M = len(S)
N = M + K
MAXN = N + 2
fact = [1]
for i in range(1,MAXN + 1):
    fact.append(fact[-1]*i%MOD)
inv_fact = [-1] * (MAXN + 1)
inv_fact[-1] = pow(fact[-1],MOD - 2,MOD)
for i in range(MAXN - 1,-1,-1):
    inv_fact[i] = inv_fact[i + 1]*(i + 1)%MOD

nck = lambda N,K: 0 if K > N or K < 0 else fact[N]*inv_fact[N - K]*inv_fact[K]%MOD

power25 = [1]
power26 = [1]
for i in range(N):
    power25.append(power25[-1]*25%MOD)
    power26.append(power26[-1]*26%MOD)

ans = 0
for i in range(M,N + 1):
    ans += nck(i - 1,M - 1) * power25[i - M] * power26[N - i] % MOD
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    K = int(input())
    S = input()
    
    M = len(S)
    N = M + K
    MAXN = N + 2
    fact = [1]
    for i in range(1,MAXN + 1):
        fact.append(fact[-1]*i%MOD)
    inv_fact = [-1] * (MAXN + 1)
    inv_fact[-1] = pow(fact[-1],MOD - 2,MOD)
    for i in range(MAXN - 1,-1,-1):
        inv_fact[i] = inv_fact[i + 1]*(i + 1)%MOD
    
    nck = lambda N,K: 0 if K > N or K < 0 else fact[N]*inv_fact[N - K]*inv_fact[K]%MOD
    
    power25 = [1]
    power26 = [1]
    for i in range(N):
        power25.append(power25[-1]*25%MOD)
        power26.append(power26[-1]*26%MOD)
    
    ans = 0
    for i in range(M,N + 1):
        ans += nck(i - 1,M - 1) * power25[i - M] * power26[N - i] % MOD
        ans %= MOD
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    mod = 10**9+7
    K = int(input())
    S = input()
    Nk = len(S)
    ret = 0
    nCk = 1
    pw25 = 1
    pw26 = pow(26,K,mod)
    inv26 = pow(26,mod-2,mod)
    for i in range(K+1):
        ret += nCk * pw25 * pw26
        ret %= mod
        nCk *= (i+Nk) * pow(i+1,mod-2,mod)
        nCk %= mod
        pw25 = (pw25*25)%mod
        pw26 = (pw26*inv26)%mod

    print(ret)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    mod = 10**9+7
    K = int(input())
    S = input()
    Nk = len(S)
    ret = 0
    nCk = 1
    for i in range(K+1):
        ret += nCk * pow(25,i,mod) * pow(26,K-i,mod)
        ret %= mod
        nCk *= (i+Nk) * pow(i+1,mod-2,mod)
        nCk %= mod
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

mod = 10**9+7
N = 10**6                   # 出力の制限
g1 = [1]*(N+1)              # 元テーブル
g2 = [1]*(N+1)              # 逆元テーブル
for i in range( 2, N + 1 ): # 準備
    g1[i] = ( g1[i-1] * i ) % mod
    g2[i] = ( g2[i-1] * pow(i,mod-2,mod) ) % mod

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

def main():
    K = int(input())
    S = input()
    Nk = len(S)
    ret = 0
    for i in range(K+1):
        ret += nCr(i+Nk-1, Nk-1, mod) * pow(25,i,mod) * pow(26,K-i,mod)
        ret %= mod
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    K = int(input())
    S = input()
    N = len(S)
    M = N+K
    # print(N,K,M)
    p = 10**9+7
    a = [None] * (M+1)
    inva = [None] * (M+1)
    a[0] = 1
    
    for i in range(1, M+1):
        a[i] = i * a[i-1] % p
    
    inva[M] = pow(a[M],p-2,p)
    for i in range(M):
        inva[M-i-1] = inva[M-i] * (M-i) % p

    ans = 0
    for i in range(K+1):
        tmp = a[N+K-i-1]*inva[N-1]%p
        tmp = tmp*inva[K-i]%p
        tmp *= pow(25,K-i,p)
        tmp %= p
        tmp *= pow(26,i,p)
        tmp %= p
        ans = ans + tmp
        ans %= p
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce


def combination(n, r, mod):
    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) % mod


n = int(input())
s = input()

S = len(s)
ans = 0
mod = 10 ** 9 + 7

for i in range(0, n+1):
    com = combination(S-1+i, S-1, mod)
    exp26 = pow(26, n-i, mod)
    exp25 = pow(25, i, mod)

    ans += (com * exp26 * exp25) % mod

ans %= mod

print(ans)

Submission status: Time Limit Exceeded

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

FAC = [1]
INV = [1]
for i in range(1,len(s)+k+1):
  FAC.append((FAC[i-1]*i) % MOD)
  INV.append(pow(FAC[-1],MOD-2,MOD))

def nCr(n,r):
  return FAC[n]*INV[n-r]*INV[r]

ans = 0
for i in range(len(s),len(s)+k+1):
  tmp = nCr(i-1,len(s)-1)*pow(25,i-len(s),MOD)
  tmp %= MOD
  tmp *= pow(26,len(s)+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

FAC = [1]
INV = [1]
for i in range(1,len(s)+k+1):
  FAC.append((FAC[i-1]*i) % MOD)
  INV.append(pow(FAC[-1],MOD-2,MOD))

def nCr(n,r):
  return FAC[n]*INV[n-r]*INV[r]

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

Submission status: Time Limit Exceeded

Solution code:
def extgcd(x, y):
    return _extgcd(x, 1, 0, y, 0, 1)

def _extgcd(x, a, b, y, c, d):
    if y == 0:
        return (x, a, b)
    k = x // y
    return _extgcd(y, c, d, x % y, a - k * c, b - k * d)

def inverse(x, m):
    _, a, _ = extgcd(x, m)
    a %= m
    return a

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

MOD = int(1e9+7)
n = len(s)
comb = [0 for _ in range(n + k + 1)]
comb[0] = 1
for i in range(n + k):
    comb[i + 1] = comb[i]
    comb[i + 1] *= (n + k - i)
    comb[i + 1] *= inverse(i + 1, MOD)
    comb[i + 1] %= MOD

ans = pow(26, n + k, MOD)
for i in range(n):
    ans -= comb[i] * pow(25, n + k - i, MOD)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

MOD = int(1e9+7)
n = len(s)
inv = [pow(i, MOD - 2, MOD) for i in range(n + k + 1)]
comb = [0 for _ in range(n + k + 1)]
comb[0] = 1
for i in range(n + k):
    comb[i + 1] = comb[i]
    comb[i + 1] *= (n + k - i)
    comb[i + 1] *= inv[i + 1]
    comb[i + 1] %= MOD

ans = pow(26, n + k, MOD)
for i in range(n):
    ans -= comb[i] * pow(25, n + k - i, MOD)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

MOD = int(1e9+7)
n = len(s)
inv = [pow(i, MOD - 2, MOD) for i in range(n + k + 1)]

def c(n, r):
    x = 1
    for i in range(r):
        x *= n - i
        x *= inv[i + 1]
        x %= MOD
    return x

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

Submission status: Time Limit Exceeded

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

m = 1000000007

l = len(S)
result = 0

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

Submission status: Time Limit Exceeded

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

m = 1000000007

l = len(S)
result = 0

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

Submission status: Time Limit Exceeded

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

m = 1000000007

l = len(S)
result = 0

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

Submission status: Time Limit Exceeded

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

m = 1000000007

result = 0
a = 1
b = 1

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