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 copy

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

def main():
    k = int(input())
    s = input()
    mod = 10**9+7
    z = [1]
    for i in range(1,k+1):
        y = z[-1]*26
        z.append(y%mod)
    #print(z)
    l = len(s)

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

Submission status: Time Limit Exceeded

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

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

def comb(n, k):
    return f[n] * f_inv[k] * f_inv[n-k] % mod

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

def main():
    k = int(input())
    s = input()
    mod = 10**9+7
    z = [1]
    for i in range(1,k+1):
        y = z[-1]*26
        z.append(y%mod)
    l = len(s)

    N = k+2
    inv_t = [0]+[1]
    for i in range(2,N):
        inv_t.append(inv_t[mod % i] * (mod - int(mod / i)) % mod)
    #print(inv_t)
    
    ans = 0
    p = 1   #pow(25,i-len(s),mod)
    q = z[k]
    bai = 1
    for i in range(l,l+k+1):
        #base = p*q   #pow(26,len(s)+k-i,mod)
        #base = pow(25,i-len(s),mod) * pow(26,len(s)+k-i,mod)
        #bai = r
        #bai = com(i-1,len(s)-1,mod)
        #print(i,len(s),base,bai)
        ans += p*q*bai
        ans %= mod
        p *= 25
        q = z[l+k-i-1]
        bai = bai*i*inv_t[i+1-l]
        bai %= mod
    print(ans)
    
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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

ans = 0
comb = 1
for i in range(k+1):
    if i > 0: comb = comb * (n+i-1) * pow(i, MOD-2, MOD) % MOD
    ans = (ans + comb * pow(25, i, MOD) * pow(26, k-i, MOD)) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

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

def make_tables(n, mod = 10 ** 9 + 7):
    fac = [1, 1] # 階乗テーブル
    finv = [1, 1] #逆元の階乗テーブル
    inv = [0, 1] #逆元テーブル

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

def nCk(n, k, mod = 10 ** 9 + 7):
    k = min(k, n-k)
    return fac[n] * finv[k] * finv[n-k] % mod

##########################
fac, finv = make_tables(10**7)
ans = 0
for i in range(k + 1):
    temp = 1
    temp *= pow(26, i, mod)
    temp %= mod
    j = k - i
    if j == 0:
        ans += temp
        continue
    temp *= pow(25, j, mod)
    temp %= mod
    temp *= nCk(n + j - 1, n - 1)
    ans += temp
    ans %= mod
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
class BiCoeff(object):
    def __init__(self, MAX, m):
        super(BiCoeff, self).__init__()
        fac = [0]*MAX
        finv = [0]*MAX
        inv = [0]*MAX

        fac[0] = 1
        fac[1] = 1
        finv[0] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2,MAX):
            fac[i] = (fac[i-1]*i)%m
            inv[i] = m - (inv[m%i] * (m//i))%m
            finv[i] = (finv[i-1] * inv[i])%m

        self.MAX = MAX
        self.m = m
        self.fac = fac
        self.finv = finv
        self.inv = inv

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

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

b = BiCoeff(n+k+10,mod)
res = 0
for i in range(n,k+n+1):
    res += b.calc(n+k,i)*pow(25,n+k-i,mod)
    res %= mod
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

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

def make_tables(n, mod = 10 ** 9 + 7):
    fac = [1, 1] # 階乗テーブル
    finv = [1, 1] #逆元の階乗テーブル
    inv = [0, 1] #逆元テーブル

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

def nCk(n, k, mod = 10 ** 9 + 7):
    k = min(k, n-k)
    return fac[n] * finv[k] * finv[n-k] % mod

##########################
fac, finv = make_tables(10**7)
ans = 0
for i in range(k + 1):
    temp = 1
    temp *= pow(26, i, mod)
    temp %= mod
    j = k - i
    if j == 0:
        ans += temp
        continue
    temp *= pow(25, j, mod)
    temp %= mod
    temp *= nCk(n + j - 1, n - 1)
    ans += temp
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
from numba import njit


def read():
    K = int(input().strip())
    S = input().strip()
    return K, S


def binom_preprocess(n, MOD=10**9+7):
    f = [0 for i in range(n+1)]  # n!
    invf = [0 for i in range(n+1)]  # (n!)^-1
    f[0] = 1
    f[1] = 1
    invf[0] = 1
    invf[1] = 1
    for i in range(2, n+1):
        f[i] = f[i-1] * i % MOD
    invf[n] = pow(f[n], MOD-2, MOD)
    for i in range(n, 2, -1):
        invf[i-1] = invf[i] * i % MOD
    return f, invf


def binom(n, k, f, invf, MOD=10**9+7):
    if n < k or n < 0 or k < 0:
        return 0
    else:
        return (f[n] * invf[k] % MOD) * invf[n-k] % MOD


def solve(K, S, MOD=10**9+7):
    T = len(S)
    f, invf = binom_preprocess(K+T+1)
    ans = 0
    for i in range(K+1):
        ans += pow(25, i, MOD) * binom(T-1+i, i, f, invf, MOD) * pow(26, K-i, MOD)
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


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


mod = 10 ** 9 + 7
fact, fact_inv, inv = fact_table(2*10**6 + 5, mod)


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


k = int(input())
S = input()
s_length = len(S)
full_length = len(S) + k
ans = 0
for i in range(k+1):
    add = pow(26, i, mod) * pow(25, k-i, mod) * nCr(full_length-i-1, s_length-1) % mod
    ans = (ans + add) % mod

print(ans)

Submission status: Time Limit Exceeded

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

l = len(s)
mod = 10**9+7 #出力の制限

n = l+k
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
for i in range( 2, n + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y/2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

ans = 0
for i in range(l,l+k+1):
    ans = (ans+cmb(i-1,l-1)*power(25,k-(l+k-i))*power(26,l+k-i)) % mod

print(ans)

Submission status: Time Limit Exceeded

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

mod = int(1e9 + 7)

def memorize(f):
    dic = {}
    def main(*args):
        if args not in dic:
            dic[args] = f(*args)
        return dic[args]
    return main
    
@memorize
def fpow(x, n):
    ret = 1
    tmp = x
    while n:
        if n & 1:
            ret = ret * tmp % mod
        tmp = tmp * tmp % mod
        n >>= 1
    return ret
    
@memorize
def inv(x):
    return fpow(x, mod - 2)
    
@memorize
def fact(x):
    ret = 1
    for i in range(1, x + 1):
        ret = ret * i % mod
    return ret
    
@memorize
def C(n, m):
    return fact(n) * inv(fact(m)) * inv(fact(n - m)) % mod
    
ret = 0
for i in range(S, S + K + 1):
    ret = (ret + C(i - 1, i - S) * fpow(25, i - S) * fpow(26, S + K - i)) % mod
print(ret)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

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

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

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

p = 10 ** 9 + 7
mod = 10 ** 9 + 7
N = 2 * 10 ** 6 + 1  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

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

ans = 0
p = N + K - 1
#now = combinations_count(p, N - 1) % mod

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

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7

SIZE = 2 * 10 ** 6 + 5
fact = [0] * SIZE
inv = [0] * SIZE
finv = [0] * SIZE
fact[0], fact[1] = 1, 1
inv[1] = 1
finv[0], finv[1] = 1, 1
for i in range(2, SIZE):
    fact[i] = fact[i - 1] * i % mod
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    finv[i] = finv[i - 1] * inv[i] % mod


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


k = int(input())
S = input()
s_length = len(S)
full_length = len(S) + k
ans = 0
for i in range(k+1):
    add = pow(26, i, mod) * pow(25, k-i, mod) * nCr(full_length-i-1, s_length-1) % mod
    ans = (ans + add) % mod

print(ans)

Submission status: Time Limit Exceeded

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

MAX = 2 * 10 ** 6

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

inv = [1] * (MAX + 1)
for i in range(2, MAX + 1):
    inv[i] = inv[mod % i] * (mod - mod // i) % mod

fact_inv = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod


def comb(n, k):
    if n < k:
        return 0
    return fact[n] * fact_inv[n-k] * fact_inv[k] % mod


ln = len(s)

ans = 0
pow25 = 1
pow26 = pow(26, k, mod)
inv26 = pow(26, mod - 2, mod)
for i in range(ln, k + ln + 1):
    ans += pow25 * pow26 % mod * comb(i - 1, ln - 1) % mod
    ans %= mod
    pow25 *= 25
    pow25 %= mod
    pow26 *= inv26
    pow26 %= mod

print(ans)

Submission status: Time Limit Exceeded

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

MAX = 2 * 10 ** 6

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

inv = [1] * (MAX + 1)
for i in range(2, MAX + 1):
    inv[i] = inv[mod % i] * (mod - mod // i) % mod

fact_inv = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod


def comb(n, k):
    if n < k:
        return 0
    return fact[n] * fact_inv[n-k] * fact_inv[k] % mod


ln = len(s)

ans = 0
pow25 = 1
pow26 = pow(26, k, mod)
inv26 = pow(26, mod - 2, mod)
for i in range(ln, k + ln + 1):
    ans += pow25 * pow26 * comb(i - 1, ln - 1)
    ans %= mod
    pow25 *= 25
    pow25 %= mod
    pow26 *= inv26
    pow26 %= mod

print(ans)

Submission status: Time Limit Exceeded

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

MAX = 2 * 10 ** 6

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

inv = [1] * (MAX + 1)
for i in range(2, MAX + 1):
    inv[i] = inv[mod % i] * (mod - mod // i) % mod

fact_inv = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod


def comb(n, k):
    if n < k:
        return 0
    return fact[n] * fact_inv[n-k] * fact_inv[k] % mod


ln = len(s)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def modpow(x, n, p):
    res = 1
    while n > 0:
        if n & 1:
            res = res * x % p
        x = x * x % p
        n >>= 1
    return res

MOD = pow(10, 9) + 7

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

n = len(s)

fact = [1 for _ in range(n + k + 1)]
p25 = [1 for _ in range(n + k + 1)]
for i in range(1, n + k + 1):
    fact[i] = fact[i - 1] * i % MOD
    p25[i] = p25[i - 1] * 25 % MOD

inv = [1 for _ in range(n + k + 1)]
inv[n + k] = modpow(fact[n + k], MOD - 2, MOD)
for i in range(n + k - 1, -1, -1):
    inv[i] = inv[i + 1] * (i + 1) % MOD

ans = modpow(26, n + k, MOD)
for i in range(n):
    ans -= fact[n + k] * inv[i] % MOD * inv[n + k - i] % MOD * p25[n + k - i] % MOD
    if ans < 0:
        ans += MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
from numba import njit


def read():
    K = int(input().strip())
    S = input().strip()
    return K, S


def binom_preprocess(n, MOD=10**9+7):
    f = [0 for i in range(n+1)]  # n!
    invf = [0 for i in range(n+1)]  # (n!)^-1
    f[0] = 1
    f[1] = 1
    invf[0] = 1
    invf[1] = 1
    for i in range(2, n+1):
        f[i] = f[i-1] * i % MOD
    invf[n] = pow(f[n], MOD-2, MOD)
    for i in range(n, 2, -1):
        invf[i-1] = invf[i] * i % MOD
    return f, invf


def binom(n, k, f, invf, MOD=10**9+7):
    if n < k or n < 0 or k < 0:
        return 0
    else:
        return (f[n] * invf[k] % MOD) * invf[n-k] % MOD


def solve(K, S, MOD=10**9+7):
    T = len(S)
    f, invf = binom_preprocess(K+T+1)
    ans = 0
    for i in range(K+1):
        L = pow(25, i, MOD) * binom(T-1+i, i, f, invf, MOD) % MOD
        R = pow(26, K-i, MOD)
        ans += L * R
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Time Limit Exceeded

Solution code:
import copy

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

def main():
    k = int(input())
    s = input()
    mod = 10**9+7
    z = [1]
    for i in range(1,k+1):
        y = z[-1]*26
        z.append(y%mod)
    #print(z)
    l = len(s)

    P = 10**9 + 7
    N = k+2
    inv_t = [0]+[1]
    for i in range(2,N):
        inv_t += [inv_t[P % i] * (P - int(P / i)) % P]
    #print(inv_t)
    
    ans = 0
    p = 1   #pow(25,i-len(s),mod)
    q = z[k]
    bai = 1
    for i in range(l,l+k+1):
        base = p*q   #pow(26,len(s)+k-i,mod)
        #base = pow(25,i-len(s),mod) * pow(26,len(s)+k-i,mod)
        #bai = r
        #bai = com(i-1,len(s)-1,mod)
        #print(i,len(s),base,bai)
        ans += base*bai
        ans %= mod
        p *= 25
        q = z[l+k-i-1]
        bai = bai*i*inv_t[i+1-l]
    print(ans)
    
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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

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


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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def modpow(x, n, p):
    res = 1
    while n > 0:
        if n & 1:
            res = res * x % p
        x = x * x % p
        n >>= 1
    return res

MOD = pow(10, 9) + 7

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

n = len(s)

fact = [1 for _ in range(n + k + 1)]
p25 = [1 for _ in range(n + k + 1)]
for i in range(1, n + k + 1):
    fact[i] = fact[i - 1] * i % MOD
    p25[i] = p25[i - 1] * 25 % MOD

inv = [1 for _ in range(n + k + 1)]
inv[n + k] = modpow(fact[n + k], MOD - 2, MOD)
for i in range(n + k - 1, -1, -1):
    inv[i] = inv[i + 1] * (i + 1) % MOD

ans = modpow(26, n + k, MOD)
for i in range(n):
    ans -= fact[n + k] * inv[i] * inv[n + k - i] * p25[n + k - i]
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def modpow(x, n, p):
    res = 1
    while n > 0:
        if n & 1:
            res = res * x % p
        x = x * x % p
        n >>= 1
    return res

MOD = pow(10, 9) + 7

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

n = len(s)

fact = [1 for _ in range(n + k + 1)]
p25 = [1 for _ in range(n + k + 1)]
for i in range(1, n + k + 1):
    fact[i] = fact[i - 1] * i % MOD
    p25[i] = p25[i - 1] * 25 % MOD

inv = [1 for _ in range(n + k + 1)]
inv[n + k] = modpow(fact[n + k], MOD - 2, MOD)
for i in range(n + k - 1, -1, -1):
    inv[i] = inv[i + 1] * (i + 1) % MOD

ans = modpow(26, n + k, MOD)
for i in range(n):
    ans -=  fact[n + k] * inv[i] * inv[n + k - i] * p25[n + k - i]

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
k=int(input())
S=input()
mod=10**9+7
n=len(S)
n_max=2*(10**6+1)
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
FI[n_max-1]=pow(F[n_max-1],mod-2,mod)
for i in reversed(range(n_max-1)):
  FI[i]=(FI[i+1]*(i+1))%mod
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod

P1,P2=[1],[1]
for _ in range(10**6):
  P1.append((P1[-1]*26)%mod)
  P2.append((P2[-1]*25)%mod)

ans=0
for i in range(n,n+k+1):
  ans+=comb(i-1,n-1)*P2[i-n]*P1[n+k-i]
  ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def modpow(x, n, p):
    res = 1
    while n > 0:
        if n & 1:
            res = res * x % p
        x = x * x % p
        n >>= 1
    return res

MOD = pow(10, 9) + 7

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

n = len(s)

fact = [1 for _ in range(n + k + 1)]
for i in range(1, n + k + 1):
    fact[i] = fact[i - 1] * i % MOD

inv = [1 for _ in range(n + k + 1)]
inv[n + k] = modpow(fact[n + k], MOD - 2, MOD)
for i in range(n + k - 1, -1, -1):
    inv[i] = inv[i + 1] * (i + 1) % MOD

p25 = [1 for _ in range(n + k + 1)]
for i in range(1, n + k + 1):
    p25[i] = p25[i - 1] * 25 % MOD

ans = modpow(26, n + k, MOD)
for i in range(n):
    ans = (ans - fact[n + k] * inv[i] % MOD * inv[n + k - i] % MOD * p25[n + k - i] % MOD + MOD) % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
s = input()
mod = 10 ** 9 + 7
len_total = len(s)+k
i = len_total
tmp = 1
fac = 1
total = 0
for i in range(1,len_total):
    fac = fac * i % mod
    if i == len_total-1:
        tmp = tmp * fac %mod
    if i == len(s) - 1:
        tmp = tmp * pow(fac, mod-2, mod)
    if i == len_total - len(s):
        tmp = tmp * pow(fac, mod-2, mod)
for i in range(k):
    tmp*= 25
i = len_total
while i >= len(s):
    total = total + tmp
    tmp = (tmp * 26 * (i - len(s)) * pow(25*(i-1), mod-2, mod))%mod
    i -= 1
print(total%mod)

Submission status: Time Limit Exceeded

Solution code:
def modpow(x, n, p):
    res = 1
    while n > 0:
        if n & 1:
            res = res * x % p
        x = x * x % p
        n >>= 1
    return res

MOD = pow(10, 9) + 7

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

n = len(s)

fact = [1 for _ in range(n + k + 1)]
for i in range(1, n + k + 1):
    fact[i] = fact[i - 1] * i % MOD

inv = [1 for _ in range(n + k + 1)]
inv[n + k] = modpow(fact[n + k], MOD - 2, MOD)
for i in range(n + k - 1, -1, -1):
    inv[i] = inv[i + 1] * (i + 1) % MOD

p25 = [1 for _ in range(n + k + 1)]
for i in range(1, n + k + 1):
    p25[i] = p25[i - 1] * 25 % MOD

ans = modpow(26, n + k, MOD)
for i in range(n):
    ans = (ans - fact[n + k] * inv[i] * inv[n + k - i] * p25[n + k - i] % MOD + MOD) % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def modpow(x, n, p):
    res = 1
    while n > 0:
        if n & 1:
            res = res * x % p
        x = x * x % p
        n >>= 1
    return res

MOD = pow(10, 9) + 7

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

n = len(s)

fact = [1 for _ in range(n + k + 1)]
for i in range(1, n + k + 1):
    fact[i] = fact[i - 1] * i % MOD

inv = [1 for _ in range(n + k + 1)]
inv[n + k] = modpow(fact[n + k], MOD - 2, MOD)
for i in range(n + k - 1, -1, -1):
    inv[i] = inv[i + 1] * (i + 1) % MOD

ans = modpow(26, n + k, MOD)
for i in range(n):
    ans = (ans - fact[n + k] * inv[i] * inv[n + k - i] * modpow(25, n + k - i, MOD) % MOD + MOD) % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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


result = 26 ** (k + n)

factorial = 1
factorialFactor = k + n 
denum = 1
denumFactor = 1

res = 0

MOD = 10**9 + 7

def pow(x, n):
	if n == 0:
		return 1

	if n % 2 == 0:
		y = pow(x, n // 2) % MOD
		return y * y % MOD

	return x * pow(x, n - 1) % MOD 

powers = []
powers.append(pow(25, k + 1))

for i in range(1, n):
	powers.append(25 * powers[i - 1] % MOD)

#print(powers)


for i in range(0, n):
	#print(i)
	#print(factorial)
	#print(denum)
	res += factorial * powers[len(powers)-i - 1] // denum % MOD
	#print(res)	
	factorial *= factorialFactor % MOD
	factorialFactor -= 1	
	denum *= denumFactor % MOD
	denumFactor += 1

result -= res

print(result % (MOD))

Submission status: Time Limit Exceeded

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


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

#import numpy as np
from collections import defaultdict

def main():

	mod=10**9+7

	n=II()
	s=input()
	s=len(s)

	pp=[1]
	for i in range(n+10):
		pp.append(pp[-1]*25%mod)


	nn=n+s

	comb=[1]
	for i in range(1,n+10):
		comb.append(comb[-1]*(nn-i+1)*pow(i,mod-2,mod)%mod)
	#print(comb)


	ans=0

	for i in range(n+1):
		ans+=(pp[i]*comb[i])%mod
		ans%=mod
	print(ans)












if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

k=int(input())
s=input()
lens=len(s)
mod=10**9+7
ans=0

dp=[0 for i in range(1+len(s)+k)]
dp[0]=1




l={i:1 for i in range(lens+10)}
for i in range(lens+1,lens+k+2):
    l[i]=l[i-1]*i//(i-lens)

now=1

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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


result = 26 ** (k + n)

factorial = 1
factorialFactor = k + n 
denum = 1
denumFactor = 1

res = 0

MOD = 10**9 + 7

def pow(x, n):
	if n == 0:
		return 1

	if n % 2 == 0:
		y = pow(x, n // 2) % MOD
		return y * y % MOD

	return x * pow(x, n - 1) % MOD 

powers = []
powers.append(pow(25, k + 1))

for i in range(1, n):
	powers.append(25 * powers[i - 1] % MOD)

#print(powers)


for i in range(0, n):
	#print(i)
	#print(factorial)
	#print(denum)
	res += factorial * powers[len(powers)-i - 1] // denum % MOD
	#print(res)	
	factorial *= factorialFactor
	factorialFactor -= 1	
	denum *= denumFactor
	denumFactor += 1

result -= res

print(result % (MOD))

Submission status: Time Limit Exceeded

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

p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

k=int(input())
s=input()
lens=len(s)
mod=10**9+7
ans=0

dp=[0 for i in range(1+len(s)+k)]
dp[0]=1

import math
def  mcal(n,r):
    return math.factorial(n)//math.factorial(n-r)//math.factorial(r)


l={i:1 for i in range(lens+10)}
for i in range(lens+1,lens+k+2):
    l[i]=l[i-1]*i//(i-lens)

now=1

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""
mod = 10**9+7 #出力の制限
N = 10**6*2
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % mod

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 )
# a = cmb(n,r)

k = onem()

s = input()[:-1]

kkk = pow(26,k,mod)

alpo = pow(26,k+len(s),mod)
print(((kkk)*(cmb(k+len(s)-1,k))-pow(len(s),k,mod))%mod)

Submission status: Time Limit Exceeded

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

dp=[0 for i in range(1+len(s)+k)]
dp[0]=1

import math
def  mcal(n,r):
    return math.factorial(n)//math.factorial(n-r)//math.factorial(r)

l={i:1 for i in range(lens+10)}
for i in range(lens+1,lens+k+2):
    l[i]=l[i-1]*i//(i-lens)

now=1

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 10 ** 9 + 7

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

    N = len(S)

    dp = [0] * (N + 1)
    dp[0] = 1

    for i in range(K + N):
        dp[N] = (dp[N] * 26 + dp[N - 1]) % MOD
        for j in range(N - 1, 0, -1):
            dp[j] = (dp[j] * 25 + dp[j - 1]) % MOD
        dp[0] = dp[0] * 25 % MOD

    print(dp[-1])

    # for i in range(1, K + N + 1):
    #     dp[N] = (dp[N] * 26 + dp[N - 1]) % MOD
    #     x = min(i, N)
    #     for j in range(x, x - 3, -1):
    #         dp[j] = (dp[j] * 25 + dp[j - 1]) % MOD
    #     dp[0] = dp[0] * 25 % MOD
    #
    # print(dp[-2])


if __name__ == '__main__':
    main()

# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Time Limit Exceeded

Solution code:
import copy

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

def main():
    k = int(input())
    s = input()
    mod = 10**9+7
    z = [1]
    for i in range(1,k+1):
        y = z[-1]*26
        z.append(y%mod)
    #print(z)
    l = len(s)

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