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

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
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

from collections import deque


from collections import Counter

from itertools import accumulate,combinations,permutations

from heapq import heapify,heappop,heappush


from functools import lru_cache

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
    

    K = int(input())
    
    
    
    
    s=input()
    ls=len(s)
    tot=pow(26,ls+K,mod)


    def extgcd1(a0,b0):
            u,v,a,b=1,0,a0,b0
            while b:
                t=a//b; a-=t*b; a,b=b,a; u,v=v,u-t*v
            if a!=1: return -1
            return u%b0
    
    N=ls+K
    fact=[0]*(N+1)
    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]=extgcd1(x,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()

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))





def fact_all(n,M=mod):
    f = [1]*(n+1)
    ans = 1
    for i in range(1,n+1):
        ans = (ans*i)%M
        f[i] = ans
    return f


def fact_inv_all(fact_all,M=mod):
    N = len(fact_all)
    finv = [0]*N
    finv[-1] = pow(fact_all[-1],M-2,M)
    for i in range(N-1)[::-1]:
        finv[i] = finv[i+1]*(i+1)%M
    return finv


def nCk(n,k,fact_list,inv_list,M=mod):
    return (((fact_list[n]*inv_list[k])%M)*inv_list[n-k])%M

K = I()
S = list(input())
N = len(S)

fl = fact_all(N+K+1)
il = fact_inv_all(fl)

beki25 = [1]*(N+K+1)
for i in range(1,N+K+1):
    beki25[i] = beki25[i-1]*25
    beki25[i] %= mod

beki26 = [1]*(N+K+1)
for i in range(1,N+K+1):
    beki26[i] = beki26[i-1]*26
    beki26[i] %= mod

ans = 0
for i in range(N-1,N+K):
    ans += nCk(i,N-1,fl,il)*beki25[i-N+1]*beki26[N+K-1-i]
    ans %= mod

print(ans)

Solution (Python):
from math import factorial

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


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  
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  
 
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


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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
class Factorial():
    def __init__(self, n, mod):
        self.mod = mod
        self.fct = [0 for _ in range(n + 1)]
        self.inv = [0 for _ in range(n + 1)]
        self.fct[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.fct[i + 1] = self.fct[i] * (i + 1) % mod
        self.inv[n] = pow(self.fct[n], mod - 2, mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i + 1] * (i + 1) % mod
            
    def comb(self, m, k):
        if m < k: return 0
        return self.fct[m] * self.inv[k] * self.inv[m - k] % self.mod

MOD = 1000000007
K = int(input())
S = len(input())
F = Factorial(K + S + 1, MOD)
res = 0
for i in range(S, K + S + 1):
    res += F.comb(K + S, i) * pow(25, K + S - i, MOD)
    res %= MOD
print(res)

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

MAX = 2 * 10**6 + 5
fact = [1] * (MAX + 1)  
finv = [1] * (MAX + 1)  
iinv = [1] * (MAX + 1)  
for i in range(2, MAX + 1):
    fact[i] = fact[i - 1] * i % MOD
    iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * iinv[i] % MOD


def comb(n: int, k: int) -> int:
    if n < k or n < 0 or k < 0:
        return 0
    return (fact[n] * finv[k] % MOD) * finv[n - k] % MOD


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

print(ans)

Solution (Python):
import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  




import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  




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 = ni()
S = ns()
s_len = len(S)
mod = 10 ** 9 + 7
ans = 0

total = K + s_len

rui = 1


for i in range(total, s_len - 1, -1):
    ans = (ans + cmb(total, i, mod) * rui) % mod
    
    rui = (rui * 25) % mod
print(ans)

Solution (Python):
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)

Solution (Python):
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**6*3
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)

Solution (Python):
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 = 2 * 10 ** 6 + 10 
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  
 
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

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)

Solution (Python):





















N_MAX = 2*(10**6)
MOD = 10**9 + 7
fac, finv, inv = [0]*N_MAX ,[0]*N_MAX, [0]*N_MAX
def com_init():
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, N_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


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

    com_init()

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

    print(ans%MOD)


if __name__ == "__main__":
    main()

Solution (Python):
mod = pow(10, 9)+7
k = int(input())
s = input()
n = len(s)
ans = 0
key = pow(26, k, mod)
sub = 1
c = 1
for i in range(k+1):
    ans += key*sub*c
    ans %= mod
    sub *= 25
    sub %= mod
    key = key*pow(26, mod-2, mod)%mod
    c *= (n+i)
    c *= pow(i+1, mod-2, mod)
    c %= mod
print(ans)

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

mod = 10**9+7 
fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,k+len(s)+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[r]*finv[n-r]%mod
t = len(s)
ans = 0
dp = [0]*(k+1)
dp[0] = 1
ans += pow(26,k)
for i in range(1,k+1):
    x = (nCr(t+i-1,t-1,mod)*pow(25,i,mod))%mod*pow(26,k-i,mod)%mod
    ans += x
    ans %= mod

print(ans%mod)

Solution (Python):
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)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import Counter

K = int(input())
S = input().rstrip('\n')

MOD = 10 ** 9 + 7

T = K + len(S)
fac = [1] * (T+1)
for i in range(1, T+1):
	fac[i] = fac[i-1] * i % MOD;

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

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

A = 1
l = len(S)
for i in range(K):
	A = A * 26 + pow(25, i+1, MOD) * choose(len(S)+i, i+1)
	A %= MOD



print(A%MOD)

Solution (Python):
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

K = ri()
S = rs()

class CombMod:
    def __init__(self, N):
        self.fact = [1]
        self.rfact = [1]
        for i in range(1, N+1):
            self.fact.append(self.fact[i-1]*i % mod)
            self.rfact.append(pow(self.fact[i], mod-2, mod))

    def comb(self, n, k):
        return self.fact[n]*self.rfact[k]*self.rfact[n-k] % mod

class PowMod:
	def __init__(self, N, base=[2]):
		self.mem = {}
		for b in base:
			pows = [1]
			for i in range(1, N+1):
				pows.append(pows[-1]*b % mod)
			self.mem[b] = pows

	def pow(self, b, n):
		return self.mem[b][n]

N = len(S)
cm = CombMod(K+N)
pm = PowMod(K, base=[25, 26])

ans = 0
for i in range(K+1):
	ans += cm.comb(K+N-i-1, N-1) * pm.pow(26, i) * pm.pow(25, K-i)
	ans = ans % mod
print(ans)

Solution (Python):








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()))



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)
	


	ans=0

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












if __name__ == "__main__":
	main()

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 1000000007  


class Combination(object):

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

    def __call__(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        fac = self.fac
        finv = self.finv
        mod = self.MOD
        return fac[n] * (finv[k]*finv[n-k] % mod) % mod


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

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

K = int(input())
S = str(input())
mod = 10**9+7
lens = len(S)
length = lens+K

L = 1
pow_dic = [0]*(10**6*2+1)
pow_dic[0] = 1
for i in range(1, 10**6*2+1):
    L = L*i%mod
    pow_dic[i] = L%mod
ans = 0
for rest in range(K+1):
    lenall = length-rest-1
    nlens = lens-1
    l = pow_dic[lenall]*pow(pow_dic[lenall-nlens], mod-2, mod)%mod
    r = pow_dic[nlens]
    comb = l*pow(r, mod-2, mod)%mod
    ans += pow(25, K-rest, mod)*pow(26, rest, mod)*comb%mod
    ans %= mod
print(ans%mod)

Solution (Python):
import numpy as np
import numba

@numba.njit("i8(i8,i8,i8)", cache=True)
def pow_numba(a, r, mod):
    r %= (mod-1)
    res = 1
    while r:
        if r%2:
            res = res * a % mod
        a = a * a % mod
        r //= 2
    return res

@numba.njit("UniTuple(i8,3)(i8,i8)", cache=True)
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

@numba.njit("UniTuple(i8[:],2)(i8,i8)", cache=True)
def get_table(mod, n_max):
    f = 1
    fac = [f]
    for i in range(1, n_max+1):
        f = f * i % mod
        fac.append(f)
    
    f = pow_numba(f, -1, mod)
    facinv = [f]
    for i in range(n_max, 0, -1):
        f = f * i % mod
        facinv.append(f)
    facinv.reverse()
    return np.array(fac), np.array(facinv)

@numba.njit("i8(i8,i8)", cache=True)
def solve(K, N):
    mod = 10**9+7
    fac, facinv = get_table(mod, 2020202)
    ans = 0
    for i in range(K+1):
        a = fac[N+K-1-i] * facinv[N-1] % mod * facinv[K-i] % mod
        a = a * pow_numba(25, K-i, mod) % mod * pow_numba(26, i, mod) % mod
        ans += a
    return ans % mod

K = int(input())
S = input()
N = len(S)
print(solve(K, N))

Solution (Python):
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

K = ri()
S = rs()

class CombMod:
    def __init__(self, N):
        self.fact = [1]
        self.rfact = [1]
        for i in range(1, N+1):
            self.fact.append(self.fact[i-1]*i % mod)
            self.rfact.append(pow(self.fact[i], mod-2, mod))

    def comb(self, n, k):
        return self.fact[n]*self.rfact[k]*self.rfact[n-k] % mod

N = len(S)
cm = CombMod(K+N)

pows = [1]
pows2 = [1]
p = 1
p2 = 1
for i in range(K+1):
	p = (p * 25) % mod
	p2 = (p2 * 26) % mod
	pows.append(p)
	pows2.append(p2)

ans = 0
for i in range(K+1):
	
	ans += cm.comb(K+N-i-1, N-1) * pows2[i] * pows[K-i]
	ans = ans % mod
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

mod = 10**9 + 7
K = int(input())
S = input().rstrip()

N = K + len(S)
fact = [1] * (N+1)
fact_inv = [1] * (N+1)
for i in range(1, N+1):
    fact[i] = i * fact[i-1] % mod
fact_inv[N] = pow(fact[N], mod-2, mod)
for i in range(1, N+1)[::-1]:
    fact_inv[i-1] = i * fact_inv[i] % mod
comb = lambda n, k: fact[n] * fact_inv[k] * fact_inv[n-k] % mod

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

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

Solution (Python):
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

n_ = 2 * 10**6 + 5
mod = 10**9 + 7
fun = [1] * (n_ + 1)
for i in range(1, n_ + 1):
    fun[i] = fun[i - 1] * i % mod
rev = [1] * (n_ + 1)
rev[n_] = pow(fun[n_], mod - 2, mod)
for i in range(n_ - 1, 0, -1):
    rev[i] = rev[i + 1] * (i + 1) % mod

def nCr(n, r):
    if r > n:
        return 0
    return fun[n] * rev[r] % mod * rev[n - r] % mod

def modinv(x, mod):
    a, b = x, mod
    u, v = 1, 0
    while b:
        t = a // b
        a -= t * b; a, b = b, a
        u -= t * v; u, v = v, u
    return u % mod


inv26 = modinv(26, mod)


def solve():
    k = ni()
    s = ns()
    n = len(s)
    ans = 0
    v = 1
    u = pow(26, k, mod)
    for i in range(n, n+k+1):
        ans = (ans + nCr(i-1, n-1) * v * u) % mod
        u = u * inv26 % mod
        v = v * 25 % mod
    print(ans)
    return

solve()

Solution (Python):
import sys
input = sys.stdin.readline
K = int(input())
S = list(input())[: -1]
mod = 10 ** 9 + 7

class Factorial:
  def __init__(self, n, mod):
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod

f = Factorial(10 ** 6 * 3, mod)
res = 0
for i in range(K + 1):
  
  t = f.combi(len(S) - 1 + K - i, len(S) - 1) * pow(25, K - i, mod) % mod
  t = t * pow(26, i, mod) % mod
  res += t
  res %= mod
print(res)

Solution (Python):
k = int(input())
s = input()
n = len(s)

mod = 10**9 + 7



max = 2 * 10**6 + 100
fac, finv, inv = [0]*max, [0]*max, [0]*max

def comInit(max):
    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

comInit(max)


def com(n,k):
    if(n < k):
        return 0
    if( (n<0) | (k < 0)):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

ans = 0
ex25 = [1] * (k+1)
ex26 = [1] * (k+1)
for i in range(1,k+1):
    ex25[i] = (ex25[i-1] * 25)%mod
    ex26[i] = (ex26[i-1] * 26)%mod

for i in range(k+1):
    j = k-i
    tmp = ex25[i] * com(n+i-1,i) * ex26[j]
    ans = (ans+tmp)%mod

print(ans)

Solution (Python):
M = 10 ** 9 + 7


def calc_inverse(n, law):
	if n == 1:
		return 1
	
	pre_r = law
	pre_x = 0
	pre_y = 1
	cur_r = n
	cur_x = 1
	cur_y = 0
	
	while True:
		d = pre_r // cur_r
		r = pre_r % cur_r
		
		nxt_r = r
		nxt_x = pre_x - d * cur_x
		nxt_y = pre_y - d * cur_y
		
		if nxt_r == 1:
			ret = nxt_x
			while ret < 0:
				ret += law;
			return ret;
		elif nxt_r == 0:
			return None
		
		pre_r = cur_r;
		pre_x = cur_x;
		pre_y = cur_y;
		cur_r = nxt_r;
		cur_x = nxt_x;
		cur_y = nxt_y;

facts = [1]
facts_i = [1]
def cache_facts(n, M):
	f = 1
	fi = 1
	for i in range(1, n):
		f = (f * i) % M
		fi = (fi * calc_inverse(i, M)) % M
		facts.append(f)
		facts_i.append(fi)

def cached_C(a, b, M):
	return facts[a] * facts_i[a - b] * facts_i[b] % M

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

cache_facts(K + L + 1, M)

total = pow(26, K, M)


for i in range(1, K + 1):
	total = (total + (pow(25, i, M) * cached_C(L + i - 1, L - 1, M) % M) * pow(26, K - i, M)) % M

print(total)

Solution (Python):
import sys
readline = sys.stdin.readline

P = 10 ** 9 + 7
def mod_prod(a,b):
    return (a % P) * (b % P) % P

def mod_fact(a):
    ret = 1
    for i in range(a):
        ret = ret * (i + 1) % P
    return ret

def mod_pow(a, n):
    ret = 1
    while n > 0:
        if n % 2 == 1:
            ret = ret * a % P
        a = a * a % P
        n = n >> 1
    return ret

def mod_div(a, b):
    b_inv = mod_pow(b, P - 2)
    return a * b_inv % P

def mod_comb(a,b):
    ret = 1
    b = min(b, a - b)
    for i in range(b):
        ret *= a - i
        ret %= P
    ret = mod_div(ret, mod_fact(b))
    return ret

def solve():
    K = int(readline())
    S = readline().rstrip()

    N = len(S)

    ans = 0
    cb = 1
    for i in range(K + 1):
        ans += mod_pow(25, i) * cb * mod_pow(26, K-i)
        cb = cb * mod_div(i + N - 1 + 1, i + 1) % P
        
        ans %= P
    print(ans)

solve()

Solution (Python):


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()

head = len(s)+k
ans = 0
for i in range(k+1):
    ans += cmb(head,i,mod)*pow(25,i,mod)
    ans %= mod

print(ans%mod)

Solution (Python):
import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def nCr(com_n, com_r):
    if com_n < com_r: return 0
    return fac[com_n] * ifac[com_r] % md * ifac[com_n - com_r] % md



md = 10 ** 9 + 7
n_max = 2000005
fac = [1]
for i in range(1, n_max + 1): fac.append(fac[-1] * i % md)
ifac = [1] * (n_max + 1)
ifac[n_max] = pow(fac[n_max], md - 2, md)
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1) % md

def main():
    k=II()
    s=SI()
    r=len(s)
    ans=0
    for i in range(k+1):
        ans=ans*26+pow(25,i,md)*nCr(i+r-1,r-1)%md
        ans%=md
    print(ans)

main()

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

mod = 10**9+7
N = K+S

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

factorial = 1
factorial_inv = [1, 1]
for i in range(2, N+1):
    factorial = (factorial*i)%mod
    factorial_inv.append((factorial_inv[-1]*inverse[i])%mod)

answer = 0
pow = -1
for i in range(K+1):
    if pow == -1:
        pow = 1
    else:
        pow = (pow*25)%mod
    answer = (answer+pow*factorial_inv[i]*factorial_inv[N-i])%mod
answer = (answer*factorial)%mod
print(answer)

Solution (Python):
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class Combination(object):
	def __init__(self, N, con):
		self.fac = [0] * (N + 1)
		self.inv = [0] * (N + 1)
		self.finv = [0] * (N + 1)
		self.fac[0], self.fac[1] = 1, 1
		self.inv[1] = 1
		self.finv[0], self.finv[1] = 1, 1

		
		for i in range(2, N + 1):
			self.fac[i] = self.fac[i - 1] * i % con
			self.inv[i] = self.inv[con % i] * (con - (con // i)) % con
			self.finv[i] = self.finv[i - 1] * self.inv[i] % con

	def com(self, N, k):
		return (self.fac[N] * self.finv[k] * self.finv[N - k]) % con



def main():
	K = int(input())
	S = list(input())
	N = len(S)
	C = Combination(N + K, con)
	ans = pow(26, K + N, con)
	for i in range(N):
		ans -= C.com(N + K, i) * pow(25, K + N - i, con)
		ans %= con

	print(ans)



if __name__ == '__main__':
	main()

Solution (Python):
mod=10**9+7
f=[1]
for i in range(2*10**6+7):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod
k=int(input())
s=input()
n=len(s)
ans=0
for i in range(k,-1,-1):
  ans+=comb(n+k,i)*pow(25,i,mod)
  ans%=mod
print(ans%mod)

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


def inv(a, mod):
    r = [1, 0, a]
    w = [0, 1, mod]
    while w[2] != 1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = w
        w = r_new
    x, y = w[0], w[1]    
    return (mod+x % mod) % mod


max_num = 2*10**6+1
fact = [0 for _ in range(max_num)]
ifact = [0 for _ in range(max_num)]

fact[0] = fact[1] = 1
ifact[0] = ifact[1] = 1

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

ifact[max_num-1] = inv(fact[max_num-1], mod)

for i in range(2, max_num):
    ifact[max_num-i] = (ifact[max_num-i+1] * (max_num-i+1)) % mod


def comb(x, y):
    if x < 0 or y < 0 or x < y:
        return 0
    else:
        return fact[x] * ifact[y] * ifact[x-y] % mod


pow25 = [1]
pow26 = [1]
for i in range(10**6):
    pow25.append((pow25[-1]*25) % mod)
    pow26.append((pow26[-1]*26) % mod)

ans = 0
for i in range(k+1):
    tmp = comb(n-1+i, i)*pow25[i]
    tmp %= mod
    tmp *= pow26[k-i]
    tmp %= mod
    ans += tmp
    
    ans %= mod

print(ans)

Solution (Python):


import sys, math
sys.setrecursionlimit(300000)

MOD = 1000000007  
def calc_fraction_mod(numerator, denominator):
    '''
        returns numerator / denominator (mod MOD)
    '''
    inv = pow(denominator, MOD - 2, MOD)
    return numerator * inv % MOD

def make_facts(n):
    '''
        make factorials
        0!(=1), 1!, 2!, 3! .... n!
    '''
    fact = [1]
    for i in range(n):
        fact.append((fact[i] * (i + 1)) % MOD)
    return fact


def make_combs(n, k):
    '''
        make [C(n - k, 0), C(n - k + 1, 1), C(n, 2) ..... C(n, k)]
    '''
    facts = make_facts(n)
    invs = [] 
    for fact in facts:
        invs.append(pow(fact, MOD - 2, MOD))

    ret = []
    for i in range(0, k + 1):
        x = n - k + i
        a = facts[x]
        
        
        
        ret.append(a * invs[i] * invs[x - i] % MOD)
    return ret

def solve(K: int, S: str):
    n = len(S)
    N = K + n
    ret = 0
    p26 = [1]
    p25 = [1]
    for i in range(1, K + 1):
        
        
        p26.append(p26[-1] * 26 % MOD)
        p25.append(p25[-1] * 25 % MOD)
    coms = make_combs(N - 1, K)
    
    
    for i in range(K + 1):
        
        tmp = p26[i] * p25[K - i] * coms[K - i]
        
        ret += tmp
        ret %= MOD
    print(ret)
    return


def solve_(K: int, S: str):
    n = len(S)
    N = K + n
    coms = make_combs(N, n)
    ret = pow(26, N, MOD)
    tmp = pow(25, coms[n], MOD)
    print(coms[n], ret, tmp)
    ret -= tmp
    
    ret %= MOD
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  
    S = next(tokens)  
    solve(K, S)

if __name__ == '__main__':
    main()

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

nagasa = len(s)


ans = pow(26, k, mod)
bunbo = 1
bunshi = 1
for i in range(1, k + 1):
    bunbo *= nagasa - 1 + i
    bunshi *= pow(i, mod - 2, mod)
    bunbo %= mod
    bunshi %= mod
    temp = bunbo * bunshi
    temp %= mod
    temp *= pow(25, i, mod)
    temp %= mod
    temp *= pow(26, k - i, mod)
    temp %= mod
    ans += temp
    ans %= mod

print(ans)