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

fac = [0] * (MAX+1)
finv = [0] * (MAX+1)
inv = [0] * (MAX+1)

def comb_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX+1):
        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 comb(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


if __name__ == '__main__':
    k = int(input())
    s = input()
    n = len(s)
    comb_init()
    ans = 0
    for i in range(k+1):
        val = comb(i+n-1, n-1)
        val *= pow(25, i, MOD)
        val %= MOD
        val *= pow(26, k-i, MOD)
        val %= MOD
        ans += val
        ans %= MOD
    print(ans)

Submission status: Accepted

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


def mod_inv(n):
    return pow(n, MOD - 2, MOD)

total = pow(26, k + s, MOD)
tmp = pow(25, k + s, MOD)
total = (total - tmp) % MOD

for i in range(0, s-1):
    tmp = ((tmp * ((k+s) - i)) % MOD * mod_inv((i + 1) * 25)) % MOD
    total = (total - tmp) % MOD
print(total)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
 
S = len(s)
mod = 10 ** 9 + 7
 
tmp_ans = pow(26, n, mod)
div = pow(26, -1, mod)
 
ans = tmp_ans
 
for i in range(1, n+1):
    tmp_ans = (tmp_ans * 25 * div) % mod
    tmp_ans = ((tmp_ans * (S-1+i)) * pow(i, -1, mod)) % mod
    ans = (ans + tmp_ans) % mod
 
ans %= mod
 
print(ans)

Submission status: Accepted

Solution code:
import sys

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

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

inv = [0] * (N_MAX + 2)
inv[0] = 0  # 逆元テーブル計算用テーブル
inv[1] = 1

for i in range(2, N_MAX + 2):
    q, r = divmod(MOD, i)
    inv[i] = -inv[r] * q % MOD


# K 文字追加
ans = 0

ln = len(S)

p = pow(26, K, MOD)

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

    ans += p % MOD
    ans %= MOD

    # pre
    p = p * (ln + i - 1) * inv[i] * 25 * inv[26] % MOD

    # suf
    # s2 = (s2 * inv[26]) % MOD

print(ans)

Submission status: Accepted

Solution code:
import sys

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

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

inv = [0] * (N_MAX + 2)
inv[0] = 0  # 逆元テーブル計算用テーブル
inv[1] = 1

for i in range(2, N_MAX + 2):
    inv[i] = -inv[MOD % i] * (MOD // i) % MOD

# K 文字追加
ans = 0

ln = len(S)

p1 = 1
p2 = 1
s2 = pow(26, K, MOD)

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

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

    # print(p1, p2, s2)

    # pre
    p1 = (p1 * (ln + i - 1) * inv[i]) % MOD
    p2 = (p2 * 25) % MOD

    # suf
    s2 = (s2 * inv[26]) % MOD

print(ans)

Submission status: Accepted

Solution code:
import sys

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

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

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

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

# K 文字追加
ans = 0

ln = len(S)

p1 = 1
p2 = 1
s2 = pow(26, K, MOD)

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

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

    # print(p1, p2, s2)

    # pre
    p1 = (p1 * (ln + i - 1) * inv[i]) % MOD
    p2 = (p2 * 25) % MOD

    # suf
    s2 = (s2 * inv[26]) % MOD

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
K = int(input())
N = len(input().rstrip())
mod = 10**9 + 7
pow25 = [1]
pow26 = [1]
x = 1
y = 1
for i in range(K):
    x *= 25
    y *= 26
    x %= mod
    y %= mod
    pow25.append(x)
    pow26.append(y)

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

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

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

Submission status: Accepted

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

mod = 10 ** 9 + 7
div = pow(26, -1, mod)
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 * div) % mod
  ans = (ans + comb_i) % mod
  
print(ans)

Submission status: Accepted

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

mod = 10**9+7
MAX_N = 10**7 + 10

fact = [1]
fact_inv = [0]*(MAX_N+4)
for i in range(MAX_N+3):
    fact.append(fact[-1]*(i+1)%mod)

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


def mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod

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

n = len(s)-1

res = 0

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

print(res)

Submission status: Accepted

Solution code:
import collections
import heapq

from collections import defaultdict
from heapq import heappush, heappop
import sys


def main(K, N):
    P = 10 ** 9 + 7

    P25 = [1] * (K + 1)
    P26 = [1] * (K + 1)
    F = [1] * (N + K)
    INV = [1] * (N + K)
    INVF = [1] * (N + K)

    p25 = 1
    p26 = 1
    for i in range(1, K + 1):
        p25 *= 25
        p25 %= P
        P25[i] = p25

        p26 *= 26
        p26 %= P
        P26[i] = p26

    f = 1
    invf = 1
    for i in range(2, N + K):
        f *= i
        f %= P
        F[i] = f
        q, r = divmod(P, i)
        INV[i] = -INV[r] * q % P
        invf *= INV[i]
        invf %= P
        INVF[i] = invf

    def comb_rep(n, r):
        return (F[n + r - 1] * INVF[r] % P) * INVF[n - 1] % P

    ret = 0
    for i in range(K + 1):
        ret += (
            P25[i] *
            P26[K - i] % P *
            comb_rep(N, i) % P
        )
    return (ret % P)


if sys.argv[-1] == 'ONLINE_JUDGE':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8,i8)')(main)
    cc.compile()
    exit()
else:
    from my_module import main
    K = int(input())
    S = input()
    print(main(K, len(S)))

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
#input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

len_S = len(S)

#MOD = 10 ** 9 + 7
SIZE = 2 * 10 ** 6 + 100
g1, g2, inv = [1, 1], [1, 1], [0, 1]
for i in range(2, SIZE + 1):
    g1.append((g1[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    g2.append((g2[-1] * inv[-1]) % MOD)
def nCr(n, r):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n - r] % MOD

answer = 0
for i in range(K + 1):
    answer += pow(25, i, MOD) * nCr(len_S - 1 + i, i) * pow(26, K - i, MOD)
    answer %= MOD

print(answer)

Submission status: Accepted

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 = pow(25,i,mod)
        tmp *= nCr(i+n-1,n-1)
        tmp *= pow(26,K-i,mod)
        ans += tmp
        ans %= mod
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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
  
pow25=pow(25,K,MOD)
inv25=invmod(25)
pow26=1
answer=0
for i in range(K+1):
  answer+=comb_mod_table(K+len_S-i-1,len_S-1)*pow25*pow26
  pow25=pow25*inv25%MOD
  pow26=pow26*26%MOD
  answer%=MOD
  
print(answer)

Submission status: Accepted

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

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)
pow25=pow(25,K+len_S,MOD)
inv25=invmod(25)
for i in range(len_S):
  answer-=comb_mod_table(K+len_S,i)*pow25
  pow25=pow25*inv25%MOD
  answer%=MOD
  
print(answer)

Submission status: Accepted

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

MAX = 2 * 10**6 + 10
MOD = 10**9+7

fac = [1] * MAX
f_inv = [1] * MAX

def prepare(n, mod):
    for i in range(1, n+1):
        fac[i] = (fac[i-1] * i) % mod
    
    f_inv[n] = pow(fac[n], -1, MOD)
    for i in range(n-1, 0, -1):
        f_inv[i] = (f_inv[i+1] * (i+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 + 5, MOD)

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

        pow25 *= 25
        pow25 %= MOD
        pow26 *= inv26
        pow26 %= MOD

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

    return(dp[1])


k = int(input())
s = input()
length = len(s)
MOD = 10**9 + 7
div = pow(26, -1, MOD)

dp = [pow(26, k, MOD)] * 2

print(solve(k, length, MOD, div, dp))

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)+5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
    
K=int(input())
s=input()
S=len(s)

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

Submission status: Accepted

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), cache=True)
def pow(n):
    l, now, mod, k = np.ones(64, np.int64), 1, 10**9+7, 10**9+5
    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), cache=True)
def num_calc(n, k):
    fact, mod = np.ones(n+k+1, dtype=np.int64), 10**9+7
    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])*power[i]) % mod
    print(ans)


num_calc(n, k)

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def _cmb(N, mod):
    N1 = N + 1
    fact = [1] * N1
    inv = [1] * N1

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

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

    def cmb(a, b):
        return fact[a] * inv[b] % mod * inv[a-b] % mod
    return cmb

def resolve():
    K = int(input())
    s = input()
    ls = len(s) - 1
    mod = 10**9+7

    cmb = _cmb(ls+K, mod)

    ans = 0
    pp = 1 * pow(26, K, mod) % mod
    px = 25 * pow(26, mod-2, mod) % mod
    for i in range(K+1):
        ans = (ans + cmb(ls+i, ls) * pp % mod) % mod
        pp = pp * px % mod
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def _cmb(N, mod):
    N1 = N + 1
    fact = [1] * N1
    inv = [1] * N1

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

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

    def cmb(a, b):
        return fact[a] * inv[b] % mod * inv[a-b] % mod
    return cmb

def resolve():
    K = int(input())
    s = input()
    ls = len(s) - 1
    mod = 10**9+7

    cmb = _cmb(ls+K, mod)

    ans = 0
    p25 = 1
    p26 = pow(26, K, mod)
    p26inv = 576923081 #pow(26,  mod-2, mod)
    for i in range(K+1):
        ans = (ans + cmb(ls+i, i) * p25 % mod * p26 % mod) % mod
        p25 = p25 * 25 % mod
        p26 = p26 * p26inv % mod
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())


def resolve():
    K = int(input())
    s = input()
    ls = len(s) - 1
    mod = 10**9+7

    N = ls + K

    N1 = N + 1
    fact = [1] * N1
    inv = [1] * N1

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

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

    def cmb(a, b):
        return fact[a] * inv[b] % mod * inv[a-b] % mod

    ans = 0
    p25 = 1
    p26 = pow(26, K, mod)
    p26inv = 576923081 #pow(26,  mod-2, mod)
    for i in range(K+1):
        ans = (ans + cmb(ls+i, ls) * p25 % mod * p26 % mod) % mod
        p25 = p25 * 25 % mod
        p26 = p26 * p26inv % mod
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def _cmb(N, mod):
    N1 = N + 1
    fact = [1] * N1
    inv = [1] * N1

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

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

    def cmb(a, b):
        return fact[a] * inv[b] % mod * inv[a-b] % mod
    return cmb

def resolve():
    K = int(input())
    s = input()
    ls = len(s) - 1
    mod = 10**9+7

    cmb = _cmb(ls+K, mod)

    ans = 0
    p25 = 1
    p26 = pow(26, K, mod)
    p26inv = 576923081 #pow(26,  mod-2, mod)
    for i in range(K+1):
        ans = (ans + cmb(ls+i, ls) * p25 % mod * p26 % mod) % mod
        p25 = p25 * 25 % mod
        p26 = p26 * p26inv % mod
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def _cmb(N, mod):
    N1 = N + 1
    fact = [1] * N1
    inv = [1] * N1

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

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

    def cmb(a, b):
        return fact[a] * inv[b] % mod * inv[a-b] % mod
    return cmb

def resolve():
    K = int(input())
    s = input()
    ls = len(s) - 1
    mod = 10**9+7

    cmb = _cmb(ls+K, mod)

    ans = 0
    p25 = 1
    p26 = pow(26, K, mod)
    p26inv = 576923081 #pow(26,  mod-2, mod)
    for i in range(K+1):
        ans = (ans + cmb(ls+i, ls) * p25 * p26) % mod
        p25 = p25 * 25 % mod
        p26 = p26 * p26inv % mod
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def _cmb(N, mod):
    N1 = N + 1
    fact = [1] * N1
    inv = [1] * N1

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

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

    def cmb(a, b):
        return fact[a] * inv[b] * inv[a-b] % mod
    return cmb

def resolve():
    K = int(input())
    s = input()
    ls = len(s) - 1
    mod = 10**9+7

    cmb = _cmb(ls+K, mod)

    ans = 0
    p25 = 1
    p26 = pow(26, K, mod)
    p26inv = 576923081 #pow(26,  mod-2, mod)
    for i in range(K+1):
        ans = (ans + cmb(ls+i, ls) * p25 * p26) % mod
        p25 = p25 * 25 % mod
        p26 = p26 * p26inv % mod
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def _cmb(N, mod):
    N1 = N + 1
    fact = [1] * N1
    inv = [1] * N1

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

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

    def cmb(a, b):
        return fact[a] * inv[b] * inv[a-b] % mod
    return cmb

def resolve():
    K = int(input())
    s = input()
    ls = len(s) - 1
    mod = 10**9+7

    cmb = _cmb(ls+K, mod)

    ans = 0
    p25 = 1
    p26 = pow(26, K, mod)
    p26inv = pow(26,  mod-2, mod)
    for i in range(K+1):
        ans = (ans + cmb(ls+i, ls) * p25 * p26) % mod
        p25 = p25 * 25 % mod
        p26 = p26 * p26inv % mod
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def _cmb(N, mod):
    N1 = N + 1
    fact = [1] * N1
    inv = [1] * N1

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

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

    def cmb(a, b):
        return fact[a] * inv[b] * inv[a-b] % mod
    return cmb

def resolve():
    K = int(input())
    s = input()
    ls = len(s) - 1
    mod = 10**9+7

    cmb = _cmb(ls+K, mod)

    ans = 0
    p25 = 1
    p26 = pow(26, K, mod)
    p26inv = pow(26,  mod-2, mod)
    for i in range(K+1):
        ans += cmb(ls+i, ls) * p25 * p26
        ans %= mod
        p25 = p25 * 25 % mod
        p26 = p26 * p26inv % mod
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def _cmb(N, mod):
    N1 = N + 1
    fact = [1] * N1
    inv = [1] * N1

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

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

    def cmb(a, b):
        return fact[a] * inv[b] * inv[a-b] % mod
    return cmb

def resolve():
    K = int(input())
    s = input()
    ls = len(s) - 1
    mod = 10**9+7

    cmb = _cmb(ls+K, mod)

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def _cmb(N, mod):
    N1 = N + 1
    fact = [0] * N1
    inv = [0] * N1
    fact[0] = fact[1] = inv[0] = inv[1] = 1

    for i in range(2, N1):
        fact[i] = fact[i-1] * i % mod
        inv[i] = pow(fact[i], mod-2, mod)

    def cmb(a, b):
        return fact[a] * inv[b] * inv[a-b] % mod
    return cmb

def resolve():
    K = int(input())
    s = input()
    ls = len(s) - 1
    mod = 10**9+7

    cmb = _cmb(ls+K, mod)

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

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

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

tmp_ans = pow(26, n, mod)
div = pow(26, -1, mod)

ans = tmp_ans

for i in range(1, n+1):
    tmp_ans = (tmp_ans * 25 * div) % mod
    tmp_ans = ((tmp_ans * (S-1+i)) * pow(i, -1, mod)) % mod
    ans = (ans + tmp_ans) % mod

ans %= mod

print(ans)

Submission status: Accepted

Solution code:
## https://atcoder.jp/contests/abc171/submissions/14626518
## パクった

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

p = 10 ** 9 + 7

pow26=pow(26,k,p)
pow25=pow(26,p-1-1,p)*25%p 
ans=0
for i in range(k+1): ## i:末尾以外に入る文字数
  ans+=pow26
  ans%=p
  pow26=(pow26*pow25)%p * (len_s+i)%p * pow(i+1,p-2,p)%p
print(ans)

Submission status: Accepted

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

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]

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

ans = 0
for i in range(len(s),len(s)+k+1):
  tmp = nCr(i-1,len(s)-1)*p25[i-len(s)]
  tmp %= MOD
  tmp *= p26[len(s)+k-i]
  tmp %= MOD
  ans +=tmp
  ans %= MOD
print(ans)

Submission status: Accepted

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

m = 1000000007


def make_factorial_table(n):
    result = [0] * (n + 1)
    result[0] = 1
    for i in range(1, n + 1):
        result[i] = result[i - 1] * i % m
    return result


def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], m - 2, m) * pow(fac[k], m - 2, m) % m


fac = make_factorial_table(len(S) - 1 + K)

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

Submission status: Accepted

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

m = 1000000007

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

Submission status: Accepted

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

m = 1000000007

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

Submission status: Accepted

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

m = 1000000007

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

Submission status: Accepted

Solution code:
# フェルマーの小定理
def main():
    from builtins import pow

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

    m = 1000000007

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


main()

Submission status: Accepted

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

# a^n mod m
def modpow(a, n, m):
    x = 1
    while n > 0:
        if n & 1: x = x * a % m
        a = a * a % m
        n >>= 1
    return x

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

Submission status: Accepted

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

m = 1000000007


def make_factorial_table(n):
    result = [0] * (n + 1)
    result[0] = 1
    for i in range(1, n + 1):
        result[i] = result[i - 1] * i % m
    return result


def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], m - 2, m) * pow(fac[k], m - 2, m) % m


fac = make_factorial_table(len(S) - 1 + K)

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

Submission status: Accepted

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

mod = 10 ** 9 + 7
N = 2 * 10**6
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 )

def cmb(n, r):
  return fac[n] * ( finv[r] * finv[n-r] % mod ) % mod

p25 = [1]
p26 = [1]

for i in range(K):
  p25.append(p25[i]*25%mod)
  p26.append(p26[i]*26%mod)

ans = 0

for i in range(K+1):
  ans += ( cmb(s+K-i-1, s-1) * p25[K-i] % mod ) * p26[i] % mod
  ans %= mod

print(ans)

Submission status: Accepted

Solution code:
K = int(raw_input())
S = raw_input().strip()
L = len(S)

P = 10**9 + 7

facts = [0 for _ in xrange(L + K)]
finvs = [0 for _ in xrange(L + K)]
facts[0] = 1
for i in xrange(1, L+K):
  facts[i] = (i*facts[i-1]) % P

finvs[L+K-1] = pow(facts[L+K-1], P-2, P)
for i in xrange(L+K-2, -1, -1):
  finvs[i] = (finvs[i+1]*(i+1)) % P

ans = 0
for k in xrange(0, K+1):
  ncr = (facts[k+L-1]*finvs[k]*finvs[L-1]) % P
  ans += ncr * pow(25, k, P) * pow(26, K-k, P)
  ans %= P

print ans

Submission status: Accepted

Solution code:
K = int(input())
S = input()
s = len(S)
L = []

mod = 10 ** 9 + 7
N = 2 * 10**6
fac = [1, 1]
finv = [1, 1]
inv = [0, 1]

def cmb(n, r):
  return fac[n] * ( finv[r] * finv[n-r] % mod ) % mod
 
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 )

for i in range(K+1):
  L.append( cmb(i+s-1, s-1) * pow(25, i, mod) % mod )

ans = []

for i, x in enumerate(L):
  if i == 0:
    ans.append(x)
  else:
    ans.append( ( ans[i-1]*26%mod + x ) % mod )

print(ans[K])

Submission status: Accepted

Solution code:


MOD = 10**9+7
factorial = [1]
inverse_factorial = [0]


def modpow(a, p):
    ans = 1
    while p:
        if p&1 == 1:
            ans = (ans*a)%MOD
        a = (a*a)%MOD
        p >>= 1
    return ans


def nCr(n, r):
    if r == 0 or r == n:
        return 1
    return (((factorial[n]*inverse_factorial[n-r])%MOD)*inverse_factorial[r])%MOD


def init_nCr(max_n):
    for i in range(1, max_n+1):
        f = (factorial[-1]*i)%MOD
        factorial.append(f)
        inv_f = modpow(f, MOD-2)
        inverse_factorial.append(inv_f)


def pow(b, p):
    ans = 1
    for _ in range(p):
        ans = (ans*b)%MOD
    return ans


def pow_list(b, p):
    ans = [1]
    for _ in range(p):
        ans.append((ans[-1]*b)%MOD)
    return ans


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    K = read_int()
    S = len(input().strip())
    init_nCr(K+S)
    T = pow(26, K+S)
    pow_25 = pow_list(25, K+S)
    for i in range(S):
        T = (T-(nCr(K+S, i)*pow_25[K+S-i])%MOD)%MOD
    return T


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

Submission status: Accepted

Solution code:
def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


MOD = 10 ** 9 + 7
K = int(input())
S = input()
L = len(S)
modFacts, invs = prepare(K + L)

ans = 0
for n in range(L, L + K + 1):
    nonSi = (pow(25, n - L, MOD) * pow(26, L + K - n, MOD)) % MOD
    Si = (modFacts[n - 1] * invs[L - 1] * invs[n - 1 - (L - 1)]) % MOD
    ans += nonSi * Si
    ans %= MOD

print(ans)