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: Accepted

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


# コンビネーション
mod = 10**9+7
def cmb(n, r, mod=mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NN = 2*10**6+5 # 使うデータによって変える
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

K = int(input())
S = input().rstrip()
L = len(S)

ans = 0
t25 = 1
t26 = pow(26, K, mod)
inv26 = pow(26, mod-2, mod)
for k in range(K+1):
    ans = (ans + t25 * t26 * cmb(k+L-1, k)) % mod
    t25 = t25 * 25 % mod
    t26 = t26 * inv26 % mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

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

invfact[2200000 - 1] = pow(fact[2200000 - 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


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

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: Accepted

Solution code:
mod = 10 ** 9 + 7
max_kai = 2*10**6
kai = [1]
for i in range(1, max_kai):
    kai.append(kai[-1] * i % mod)
kkai = [0] * max_kai
kkai[-1] = pow(kai[-1], mod - 2, mod)
for i in reversed(range(1, max_kai)):
    kkai[i - 1] = kkai[i] * i % mod


def comb(a, b):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = 1
    c *= kai[a]
    c *= kkai[b]
    c *= kkai[a - b]
    return c % mod


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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

mod = 10**9+7
answer = 0
tmp = 0

# 組み合わせの数の計算は以下URLからコピーしてきた：
# https://qiita.com/derodero24/items/91b6468e66923a87f39f
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 = K+S
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 )

pow = -1
for i in range(K+1):
  if pow == -1:
    pow = 1
  else:
    pow = (pow*25)%mod
  answer = (answer+pow*cmb(N,i,mod))%mod

print(answer)

Submission status: Accepted

Solution code:
R=int(input())
s=input()
k=len(s)
n=R+k
MOD=10**9+7
factorials=[1]
current=1
for i in range(1,n+1):
  current=(current*i)%MOD
  factorials.append(current)
inverses=[]
for i in range(n+1):
  inverses.append(pow(factorials[i],MOD-2,MOD))
ans=0
for i in range(R+1):
  ans=(ans+factorials[n]*inverses[i+k]*inverses[n-i-k]*pow(25,n-k-i,MOD))%MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    K = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    s=input()
    ls=len(s)
    tot=pow(26,ls+K,mod)

    N=ls+K
    fact=[0]*(N+1)#NはnCrの最大のn
    ifact=[0]*(N+1)
    fact[0],fact[1],ifact[0],ifact[1]=1,1,1,1
    for i in range(2,N+1):
        x=(fact[i-1]*i)%mod
        fact[i]=x
        ifact[i]=pow(x,mod-2,mod)
    pows=[1]*(N+1)
    for i in range(1,N+1):
        pows[i]=pows[i-1]*25%mod

    def comb(n,r): return (fact[n]*ifact[r]%mod)*ifact[n-r]%mod
    
    for i in range(0,ls):
        tot-=comb(ls+K,i)*pows[ls+K-i]
        tot%=mod
    print(tot)
    






if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7

def main(K, N, MOD):
    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

    fact, fact_inv, inv = fact_table(2_000_010, MOD)
    f = np.zeros(K + 1, np.int64)
    f = fact[N - 1:K + N] * fact_inv[N - 1] % MOD * fact_inv[0:K + 1] % MOD
    x = 1
    for i in range(1, K + 1):
        x = (x * 25) % MOD
        f[i] = f[i] * x % MOD
    for i in range(1, K + 1):
        f[i] += f[i - 1] * 26
        f[i] %= MOD
    return f[-1]

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.from_dtype(np.int64)
    signature = (i8, i8, i8)

    cc = CC('my_module')
    cc.export('main', signature)(main)
    cc.compile()

from my_module import main

K = int(readline())
N = len(read().rstrip())

print(main(K, N, MOD))

Submission status: Accepted

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

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

C = lambda a, b: fa[a] * fainv[b] % P * fainv[a-b] % P if 0 <= b <= a else 0

s = 0
po = 1
for i in range(K + 1):
    s = (s + C(N, i) * po) % P
    po = po * 25 % P
print(s)

Submission status: Accepted

Solution code:
mod = 10**9+7
def inv(n):
    x = pow(n,mod-2,mod)
    return x
k = int(input())
s = input()
l = len(s)
cmb = 1
ans = 1
for i in range(k):
    cmb =cmb*25*(k+l-i)*inv(i+1)
    cmb %= mod
    ans += cmb
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
# import sys
# input = sys.stdin.readline
k = int(input())
s = input()
n = len(s)
mod = 10**9 + 7
l = 2*10**6 + 3

a25 = [1]
for i in range(l):
    a25.append((a25[-1] * 25) % mod)
a26 = [1]
for i in range(l):
    a26.append((a26[-1] * 26) % mod)


mod = 10**9 + 7


M = [1]  # i!のmod
m = 1
for i in range(1, l):
    m = (m * i) % mod
    M.append(m)

def pow(x, y, mod):  # x**y の mod を返す関数
    ans = 1
    while y > 0:
        if y % 2 == 1:
            ans = (ans * x) % mod
        x = (x**2) % mod
        y //= 2
    return ans

def inv(x, mod):  # x の mod での逆元を返す関数
    return pow(x, mod-2, mod)

# print(inv(8,13))

MI = [0] * (l-1) +[inv(M[l-1], mod)]  # i!の逆元
for i in range(l-2, -1, -1):
    MI[i] = MI[i+1] * (i+1) % mod

def C(x, y):  # コンビネーション
    if y < 0 or y > x:
        return 0
    elif x > l:  # O(min(y, x-y))
        y = min(y, x-y)
        ans = 1
        for i in range(x, x-y, -1):
            ans = (ans * i) % mod
        return (ans * MI[y]) % mod
    else:  # O(1)
        ans = M[x]
        ans = (ans * MI[y]) % mod
        return (ans * MI[x-y]) % mod

ans = 0
for i in range(n-1, n+k):
    ans = (ans + C(i, n-1) * a25[i-(n-1)] * a26[n+k-i-1]) % mod
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import bisect
import collections
import sys

sys.setrecursionlimit(1000000)
ACMOD = 1000000007
INF = 1 << 62

MOD = 1000000007  # type: int


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

    p = MOD
    N = K + len(S)  # N は必要分だけ用意する
    fact = [1, 1]  # fact[n] = (n! mod p)
    factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
    inv = [0, 1]  # factinv 計算用

    for i in range(2, N + 1):
        fact.append((fact[-1] * i) % p)
        inv.append((-inv[p % i] * (p // i)) % p)
        factinv.append((factinv[-1] * inv[-1]) % p)

    ans = 0
    for k in range(K + 1):
        remain = K - k
        ans += pow(26, k, MOD) * pow(25, remain, MOD) * cmb(remain + len(S) - 1, remain, MOD)
    print(ans % MOD)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(K, S)


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

Submission status: Accepted

Solution code:
FAST_IO = 0
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()
    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]

####

def solve(K, S):
    MOD = 10 ** 9 + 7
    N = len(S)
    N2 = N + K

    BIG =N2
    fac = [1, 1]
    for x in xrange(2, BIG+1):
        fac.append(fac[-1] * x  %MOD)
    inv = [1] * (BIG + 1)
    inv[BIG] = pow(fac[-1], MOD-2, MOD)
    for x in xrange(BIG-1, -1, -1):
        inv[x] = inv[x+1] * (x+1) % MOD

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

    pow25 = [1]
    for x in xrange(1, BIG + 1):
        pow25.append(pow25[-1] * 25  %MOD)

    ans = 0
    for n in xrange(N, N2 + 1):
        ans += binom(N2, n)   * pow25[N2- n] % MOD
        ans %= MOD
    return ans

print solve(rri(), rr())

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def comb(a,b):
        return f[a]*inv[b]*inv[a-b]%mod
    k = I()
    s = input()
    n = len(s)
    m = n+k
    N = 2*10**6+10**5
    f = [1]*(N+1)
    for i in range(1,N+1):
        f[i] = f[i-1]*i%mod
    inv = [None]*(N+1)
    inv[N] = pow(f[N],mod-2,mod)
    for i in range(N)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    ans = pow(26, m, mod)
    for i in range(n):
        ans -= comb(m,i)*pow(25,m-i,mod)%mod
        ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
SIZE=2*10**6; MOD=10**9+7 #998244353 #ここを変更する

SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    fac[i] = fac[i-1]*i%MOD
finv[-1] = pow(fac[-1],MOD-2,MOD)
for i in range(SIZE-1,0,-1):
    finv[i-1] = finv[i]*i%MOD
    inv[i] = finv[i]*fac[i-1]%MOD

def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0



# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

k, = map(int,readline().split())
s = input()

MOD = 10**9+7

l = len(s)
ans = pow(26,l+k,MOD)

p25 = [1]
for _ in range(SIZE):
    p25.append(p25[-1]*25%MOD)

for p in range(l):
    ans -= p25[k+l-p]*choose(l+k,p)%MOD

print(ans%MOD)

Submission status: Accepted

Solution code:
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

mod = 10**9+7 #出力の制限
N = 2*10**6
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 )

K=int(input())
S=input()
N=len(S)
ans=0
for i in range(0,K+1):
    ans+=((cmb(N-1+K-i,N-1,mod)*pow(25,K-i,mod))%mod)*pow(26,i,mod)
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7

def main(K, N, MOD):
    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

    fact, fact_inv, inv = fact_table(3_000_000, MOD)
    f = np.zeros(K + 1, np.int64)
    f = fact[N - 1:K + N] * fact_inv[N - 1] % MOD * fact_inv[0:K + 1] % MOD
    x = 1
    for i in range(1, K + 1):
        x = (x * 25) % MOD
        f[i] = f[i] * x % MOD
    for i in range(1, K + 1):
        f[i] += f[i - 1] * 26
        f[i] %= MOD
    return f[-1]

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.from_dtype(np.int64)
    signature = (i8, i8, i8)

    cc = CC('my_module')
    cc.export('main', signature)(main)
    cc.compile()

from my_module import main

K = int(readline())
N = len(read().rstrip())

print(main(K, N, MOD))

Submission status: Accepted

Solution code:
import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7

def main(K, N, MOD):
    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

    fact, fact_inv, inv = fact_table(3_000_000, MOD)
    f = np.zeros(K + 1, np.int64)
    f = fact[N - 1:K + N] * fact_inv[N - 1] % MOD * fact_inv[0:K + 1] % MOD
    x = 1
    for i in range(1, K + 1):
        x = (x * 25) % MOD
        f[i] = f[i] * x % MOD
    for i in range(1, K + 1):
        f[i] += f[i - 1] * 26
        f[i] %= MOD
    return f[-1]

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.from_dtype(np.int64)
    signature = (i8, i8, i8)

    cc = CC('my_module')
    cc.export('main', signature)(main)
    cc.compile()

from my_module import main

K = int(readline())
N = len(read().rstrip())

print(main(K, N, MOD))

Submission status: Accepted

Solution code:
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
k=N()
s=input()
n=len(s)
N=k+n
mod=10**9+7
fac=[1]*(N+3)
inv=[1]*(N+3)
t=1
for i in range(1,N+3):
    t*=i
    t%=mod
    fac[i]=t
t=pow(fac[N+2],mod-2,mod)
for i in range(N+2,0,-1):
    inv[i]=t
    t*=i
    t%=mod
def comb(n,r):
    if r>n or r<0:
        return 0
    return fac[n]*inv[n-r]*inv[r]%mod
pow26=[1]*(k+1)
pow25=[1]*(k+1)
t1=1
t2=1
for i in range(k+1):
    pow25[i]=t1
    pow26[i]=t2
    t1*=25
    t1%=mod
    t2*=26
    t2%=mod
ans=pow26[k]
for i in range(1,k+1):
    ans+=comb(n+i-1,i)*pow25[i]*pow26[k-i]
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
max_kai = 5*10**6
kai = [1]
for i in range(1, max_kai):
    kai.append(kai[-1] * i % mod)
kkai = [0] * max_kai
kkai[-1] = pow(kai[-1], mod - 2, mod)
for i in reversed(range(1, max_kai)):
    kkai[i - 1] = kkai[i] * i % mod


def comb(a, b):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = 1
    c *= kai[a]
    c *= kkai[b]
    c *= kkai[a - b]
    return c % mod


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

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

k = ni()
s = ns().strip()
mod = 1000000007

n = k + len(s)

def enumfif(n, mod):
    f = [0] * (n+1)
    invf = [0] * (n+1)
    f[0] = 1
    for i in range(1, n+1):
        f[i] = f[i-1] * i % mod

    a = f[n]
    b = mod
    p, q = 1, 0
    while b > 0:
        c = a//b
        d = a; a = b; b = d % b
        d = p; p = q; q = d-c*q
    invf[n] = p + mod if p < 0 else p
    for i in range(n-1,-1,-1):
        invf[i] = invf[i+1] * (i+1) % mod
    return f, invf

def C(n, r, mod, fif):
    if n < 0 or r < 0 or r > n:
        return 0
    return fif[0][n] * fif[1][r] * fif[1][n-r] % mod

fif = enumfif(2000005, mod)

ans = 0
v = 1
for i in range(n, len(s)-1, -1):
    ans += v * C(n, i, mod, fif)
    v = v * 25 % mod
print(ans%mod)

Submission status: Accepted

Solution code:
class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD


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

N = K + len(S)
M = len(S)
com = comb(N + 1, MOD)

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

ans = 0

for i in range(K + 1):
  ans = (ans + p25[i] * com.com(M + i  - 1, M - 1) * p26[K - i]) % MOD

print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7

@njit
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

@njit
def main(K, N, MOD):
    fact, fact_inv, inv = fact_table(3_000_000, MOD)
    f = np.zeros(K + 1, np.int64)
    f = fact[N - 1:K + N] * fact_inv[N - 1] % MOD * fact_inv[0:K + 1] % MOD
    x = 1
    for i in range(1, K + 1):
        x = (x * 25) % MOD
        f[i] = f[i] * x % MOD
    for i in range(1, K + 1):
        f[i] += f[i - 1] * 26
        f[i] %= MOD
    return f[-1]

K = int(readline())
N = len(read().rstrip())

print(main(K, N, MOD))

Submission status: Runtime Error

Solution code:
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]%mod)%mod

mod = 10**9+7

K = int(input())
S = input()
N = len(S)
max = N+K
fac = [0] * max
finv = [0] * max
inv = [0] * max
COMinit()

ans = 0
for i in range(K+1):
    x = COM(N+K-i-1,N-1)
    y = mod(26,i,mod)
    z = mod(25,K-i,mod)
    xyz = ((x*y%mod)*z)%mod
    ans = (ans+xyz)%mod
print(ans)

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

"""
dp[i][j]を
「i文字目まででj回Sの文字を使ったか」とする

K = 5
S = 'oof'
dp = [[0] * (len(S) + 1) for i in range(K + len(S) + 1)]
dp[0][0] = 1

for i in range(1, K + len(S) + 1):
    for j in range(len(S) + 1):
        if j < len(S):
            dp[i][j] += dp[i - 1][j] * 25
        else:
            dp[i][j] += dp[i - 1][j] * 26 # j回使い切るともうSは関係なくなるので *= 26になる
        if j >= 1:
            dp[i][j] += dp[i - 1][j - 1]

l_s = len(S)
どのタイミングで「この先ずっと*= 26」になるか
後ろからi文字目にSを使い切る: pow(25, K - k, mod) * cmb(N + K - k - 1, N - 1) * pow(26, k, mod)
...
"""


lim = 10 ** 6 + 1
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, lim + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    # 累計
    factinv.append((factinv[-1] * inv[-1]) % mod)

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

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

ans = 0
# l_s + i文字目に文字を使い切る
# 次から *= 26
for k in range(K + 1):
    # 逆からやってる
    ans += cmb(N + K - k - 1, N - 1) * pow(26, k, mod) * pow(25, K - k, mod) % mod
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

"""
dp[i][j]を
「i文字目まででj回Sの文字を使ったか」とする

K = 5
S = 'oof'
dp = [[0] * (len(S) + 1) for i in range(K + len(S) + 1)]
dp[0][0] = 1

for i in range(1, K + len(S) + 1):
    for j in range(len(S) + 1):
        if j < len(S):
            dp[i][j] += dp[i - 1][j] * 25
        else:
            dp[i][j] += dp[i - 1][j] * 26 # j回使い切るともうSは関係なくなるので *= 26になる
        if j >= 1:
            dp[i][j] += dp[i - 1][j - 1]

l_s = len(S)
どのタイミングで「この先ずっと*= 26」になるか
後ろからi文字目にSを使い切る: pow(25, K - k, mod) * cmb(N + K - k - 1, N - 1) * pow(26, k, mod)
...
"""


lim = 10 ** 6 + 1
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, lim + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    # 累計
    factinv.append((factinv[-1] * inv[-1]) % mod)

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

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

ans = 0
# l_s + i文字目に文字を使い切る
# 次から *= 26
for k in range(K + 1):
    # 逆からやってる
    ans += cmb(N + K - k - 1, N - 1) * pow(26, k, mod) * pow(25, K - k, mod) % mod
    ans %= mod

print(ans)

Submission status: Runtime Error

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


class Combination:
    """
  O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
  n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
  使用例：
  comb = Combination(1000000)
  print(comb(5, 3))  # 10
  """

    def __init__(self, n_max, mod=10 ** 9 + 7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n - r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n + 1):
            fac.append(fac[i - 1] * i % self.mod)
            facinv.append(facinv[i - 1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n + 1)
        modinv[1] = 1
        for i in range(2, n + 1):
            modinv[i] = self.mod - self.mod // i * \
                modinv[self.mod % i] % self.mod
        return modinv


comb = Combination(1000000)
ans = 0
for i in range(K + 1):

    temp = comb(N + K - i - 1, N - 1)
    temp %= MOD
    temp *= pow(26, i, MOD)
    temp %= MOD
    temp *= pow(25, K - i, MOD)
    temp %= MOD
    ans += temp
    ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7
MAX = 5*10**5 + 1

fact = [0 for _ in range(MAX)]
factinv = [0 for _ in range(MAX)]

fact[0] = 1
for k in range(1, MAX):
    fact[k] = fact[k - 1]*k
    fact[k] %= MOD

factinv[MAX - 1] = pow(fact[MAX - 1], MOD - 2, MOD)
for k in range(MAX - 1, 0, -1):
    factinv[k - 1] = factinv[k]*k
    factinv[k - 1] %= MOD

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

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

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

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

print(ans)

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7
MAX = 5*10**5 + 1

fact = [0 for _ in range(MAX)]
factinv = [0 for _ in range(MAX)]

fact[0] = 1
for k in range(1, MAX):
    fact[k] = fact[k - 1]*k
    fact[k] %= MOD

factinv[MAX - 1] = pow(fact[MAX - 1], MOD - 2, MOD)
for k in range(MAX - 1, 0, -1):
    factinv[k - 1] = factinv[k]*k
    factinv[k - 1] %= MOD

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

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

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

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

print(ans)

Submission status: Runtime Error

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
nmax = 10**6
mod = 10**9+7
fac = [1]*nmax
finv = [1]*nmax
inv = [1]*nmax
def ncr_pre():
    for i in range(2,nmax):
        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 ncr(n,r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fac[n]* (finv[r] * finv[n-r] %mod) %mod

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