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:
 
# from math import factorial as fac
from collections import defaultdict
# from copy import deepcopy
import sys, math
f = None
try:
	f = open('q1.input', 'r')
except IOError:
	f = sys.stdin
if 'xrange' in dir(__builtins__):
	range = xrange
# print(f.readline())
sys.setrecursionlimit(10**2)

	
def print_case_iterable(case_num, iterable):
	print("Case #{}: {}".format(case_num," ".join(map(str,iterable))))

def print_case_number(case_num, iterable):
	print("Case #{}: {}".format(case_num,iterable))

def print_iterable(A):
	print (' '.join(A))

def read_int():
	return int(f.readline().strip())
def read_int_array():
	return [int(x) for x in f.readline().strip().split(" ")]
def rns():
	a =  [x for x in f.readline().split(" ")]
	return int(a[0]), a[1].strip()
def read_string():
	return list(f.readline().strip())
def ri():
	return int(f.readline().strip())
def ria():
	return [int(x) for x in f.readline().strip().split(" ")]
def rns():
	a =  [x for x in f.readline().split(" ")]
	return int(a[0]), a[1].strip()
def rs():
	return list(f.readline().strip())
def bi(x):
	return bin(x)[2:]





from collections import deque
import math
NUMBER = 10**9 + 7
# NUMBER = 998244353
def factorial(n) : 
	M = NUMBER
	f = 1
  
	for i in range(1, n + 1):  
		f = (f * i) % M # Now f never can  
						# exceed 10^9+7  
	return f
def mult(a,b):
	return (a * b) % NUMBER

def minus(a , b):
	return (a - b) % NUMBER

def plus(a , b):
	return (a + b) % NUMBER

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)

def modinv(a):
	m = NUMBER
	g, x, y = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
def choose(n,k):
	if n < k:
		assert false
	return  mult(factorial(n), modinv(mult(factorial(k),factorial(n-k)))) % NUMBER
from collections import deque, defaultdict 
import heapq


from types import GeneratorType
def bootstrap(f, stack=[]):
	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to

	return wrappedfunc


def dfs(g, timeIn, timeOut,depths,parents): 
	# assign In-time to node u 
	cnt = 0
	# node, neig_i, parent, depth
	stack = [[1,0,0,0]]
	while stack:
		v,neig_i,parent,depth = stack[-1]
		parents[v] = parent
		depths[v] = depth
		# print (v)
		if neig_i == 0:
			timeIn[v] = cnt    
			cnt+=1
		while neig_i < len(g[v]):
			u = g[v][neig_i]
			if u == parent:
				neig_i+=1
				continue
			stack[-1][1] = neig_i + 1
			stack.append([u,0,v,depth+1])
			break
		if neig_i == len(g[v]):
			stack.pop()
			timeOut[v] = cnt
			cnt += 1
  
# def isAncestor(u: int, v: int, timeIn: list, timeOut: list) -> str: 
# 	return timeIn[u] <= timeIn[v] and timeOut[v] <= timeOut[u] 

cnt = 0
@bootstrap
def dfs(v,adj,timeIn, timeOut,depths,parents,parent=0,depth=0):
	global cnt
	parents[v] = parent
	depths[v] = depth
	timeIn[v] = cnt
	cnt+=1
	for u in adj[v]:
		if u == parent:
			continue
		yield dfs(u,adj,timeIn,timeOut,depths,parents,v,depth+1)
	timeOut[v] = cnt
	cnt+=1
	yield 


def solution(s,n):
	p = NUMBER
	summ = 0
	k = len(s)
	n = n+k
	d = 26
	mxn = 10**6
	pows = [-1]*(n-k+1)
	for i in range(n-k+1):
		pows[i] = pow(i+k,p-2,p)
	chooses = [1]*(n-k+1)
	chooses[0] = (factorial(n) * pow(factorial(k),p-2,p) * pow(factorial(n-k),p-2,p))%p
	for i in range(1,n-k+1):
		chooses[i] = (chooses[i-1] * (n-(i-1+k)) *(pows[i]))%p
	dpows = [1]*(n-k+1)
	for i in range(1,n-k+1):
		dpows[i] = pow(d-1,i,p)	
	for j in range(n-k+1):
		summ=plus(summ,mult(chooses[j],dpows[n-k-j]))
	return summ 
	
def main():
	T = 1
	# T = ri()
	for i in range(T):
		n = ri()
		s = rs()
		# a = ria()
		# n,k = ria()
		# a=ria()

		x = solution(s,n)
		if 'xrange' not in dir(__builtins__):
			print(x)
		else:
			print >>output,str(x)# "Case #"+str(i+1)+':',
	if 'xrange' in dir(__builtins__):
		print(output.getvalue())
		output.close()

if 'xrange' in dir(__builtins__):
	import cStringIO
	output = cStringIO.StringIO()
#example usage:
#    for l in res:
#       print >>output, str(len(l)) + ' ' +  ' '.join(l)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
 
# from math import factorial as fac
from collections import defaultdict
# from copy import deepcopy
import sys, math
f = None
try:
	f = open('q1.input', 'r')
except IOError:
	f = sys.stdin
if 'xrange' in dir(__builtins__):
	range = xrange
# print(f.readline())
sys.setrecursionlimit(10**2)

	
def print_case_iterable(case_num, iterable):
	print("Case #{}: {}".format(case_num," ".join(map(str,iterable))))

def print_case_number(case_num, iterable):
	print("Case #{}: {}".format(case_num,iterable))

def print_iterable(A):
	print (' '.join(A))

def read_int():
	return int(f.readline().strip())
def read_int_array():
	return [int(x) for x in f.readline().strip().split(" ")]
def rns():
	a =  [x for x in f.readline().split(" ")]
	return int(a[0]), a[1].strip()
def read_string():
	return list(f.readline().strip())
def ri():
	return int(f.readline().strip())
def ria():
	return [int(x) for x in f.readline().strip().split(" ")]
def rns():
	a =  [x for x in f.readline().split(" ")]
	return int(a[0]), a[1].strip()
def rs():
	return list(f.readline().strip())
def bi(x):
	return bin(x)[2:]





from collections import deque
import math
NUMBER = 10**9 + 7
# NUMBER = 998244353
def factorial(n) : 
	M = NUMBER
	f = 1
  
	for i in range(1, n + 1):  
		f = (f * i) % M # Now f never can  
						# exceed 10^9+7  
	return f
def mult(a,b):
	return (a * b) % NUMBER

def minus(a , b):
	return (a - b) % NUMBER

def plus(a , b):
	return (a + b) % NUMBER

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)

def modinv(a):
	m = NUMBER
	g, x, y = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
def choose(n,k):
	if n < k:
		assert false
	return  mult(factorial(n), modinv(mult(factorial(k),factorial(n-k)))) % NUMBER
from collections import deque, defaultdict 
import heapq


from types import GeneratorType
def bootstrap(f, stack=[]):
	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to

	return wrappedfunc


def dfs(g, timeIn, timeOut,depths,parents): 
	# assign In-time to node u 
	cnt = 0
	# node, neig_i, parent, depth
	stack = [[1,0,0,0]]
	while stack:
		v,neig_i,parent,depth = stack[-1]
		parents[v] = parent
		depths[v] = depth
		# print (v)
		if neig_i == 0:
			timeIn[v] = cnt    
			cnt+=1
		while neig_i < len(g[v]):
			u = g[v][neig_i]
			if u == parent:
				neig_i+=1
				continue
			stack[-1][1] = neig_i + 1
			stack.append([u,0,v,depth+1])
			break
		if neig_i == len(g[v]):
			stack.pop()
			timeOut[v] = cnt
			cnt += 1
  
# def isAncestor(u: int, v: int, timeIn: list, timeOut: list) -> str: 
# 	return timeIn[u] <= timeIn[v] and timeOut[v] <= timeOut[u] 

cnt = 0
@bootstrap
def dfs(v,adj,timeIn, timeOut,depths,parents,parent=0,depth=0):
	global cnt
	parents[v] = parent
	depths[v] = depth
	timeIn[v] = cnt
	cnt+=1
	for u in adj[v]:
		if u == parent:
			continue
		yield dfs(u,adj,timeIn,timeOut,depths,parents,v,depth+1)
	timeOut[v] = cnt
	cnt+=1
	yield 


def solution(s,n):
	# fact = [1]*(10**6+1)
	# for i in range(1,10**6+1):
	# 	fact[i] = (fact[i-1]*i)%NUMBER
	p = NUMBER
	summ = 0
	k = len(s)
	n = n+k
	d = 26
	mxn = 10**6
	pows = [-1]*(n-k+1)
	for i in range(n-k+1):
		pows[i] = pow(i+k,p-2,p)

	chooses = [1]*(n-k+1)
	chooses[0] = (factorial(n) * pow(factorial(k),p-2,p) * pow(factorial(n-k),p-2,p))%p
	for i in range(1,n-k+1):
		chooses[i] = (chooses[i-1] * (n-(i-1+k)) *(pows[i]))%p

	# chooses = [1]*(10)
	# chooses[0] = (factorial(n) * pows[0] * pow(n-k,p-2,p))%p
	# print(chooses[0])
	# for i in range(1,10):
	# 	chooses[i] = (chooses[i-1] * (n-(i-1+k)) *(pows[i]))%p
	
	dpows = [0]*(n-k+1)
	for i in range(1,n-k+1):
		dpows[i] = pow(d-1,i,p)	
	# def chooseb(l,r):
	# 	return mult(fact[l],pow(mult(fact[r],fact[l-r]),p-2,p))
	for j in range(n-k+1):
		# print(j)
		summ=plus(summ,mult(chooses[j],dpows[n-k-j]))
		# summ=mult(summ,)
	return summ + 1
	
def main():
	T = 1
	# T = ri()
	for i in range(T):
		n = ri()
		s = rs()
		# a = ria()
		# n,k = ria()
		# a=ria()

		x = solution(s,n)
		if 'xrange' not in dir(__builtins__):
			print(x)
		else:
			print >>output,str(x)# "Case #"+str(i+1)+':',
	if 'xrange' in dir(__builtins__):
		print(output.getvalue())
		output.close()

if 'xrange' in dir(__builtins__):
	import cStringIO
	output = cStringIO.StringIO()
#example usage:
#    for l in res:
#       print >>output, str(len(l)) + ' ' +  ' '.join(l)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
#!python3

LI = lambda: list(map(int, input().split()))

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

MOD = 10 ** 9 + 7
MAX = 2 * (10 ** 6) + 1
p25, p26 = [None] * MAX, [None] * MAX
fac, finv, inv = [None] * MAX, [None] * MAX, [None] * MAX


def comb_init():
    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] = -inv[MOD%i] * int(MOD / i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD


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


def power_init():
    p25[0] = 1
    p26[0] = 1
    for i in range(1, MAX):
        p25[i] = p25[i - 1] * 25 % MOD
        p26[i] = p26[i - 1] * 26 % MOD


def main():
    comb_init()
    power_init()
    n = len(S)
    ans = 0
    for i in range(K + 1):
        x = p25[i] * comb(i + n - 1, n - 1) % MOD * p26[K - i] % MOD
        ans = (ans + x) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

    def cmb1(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
    fac = [1]*(N+1)
    finv = [1]*(N+1)
    for i in range(N):
        fac[i+1] = fac[i] * (i+1) % mod
    finv[-1] = pow(fac[-1], mod-2, mod)
    for i in reversed(range(N)):
        finv[i] = finv[i+1] * (i+1) % mod

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

    def power(a, n, mod):
        bi=str(format(n,"b")) #2進数
        res=1
        for i in range(len(bi)):
            res=(res*res) %mod
            if bi[i]=="1":
                res=(res*a) %mod
        return res

    ans = 0
    for i in range(k+1):
        temp = power(25, i, mod)
        temp *= cmb1(i+n-1, n-1, mod)
        temp %= mod
        temp *= power(26, k-i, mod)
        temp %= mod
        ans += temp
    print(ans%mod)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class Combination:
    def __init__(self, n: int, mod: int):
        self.mod = mod
        self.fact = [0] * (n + 1)
        self.factinv = [0] * (n + 1)
        self.inv = [0] * (n + 1)
        
        self.fact[0] = self.fact[1] = 1
        self.factinv[0] = self.factinv[1] = 1
        self.inv[1] = 1
        for i in range(2, n + 1):
            self.fact[i] = (self.fact[i - 1] * i) % mod
            self.inv[i] = (-self.inv[mod % i] * (mod // i)) % mod
            self.factinv[i] = (self.factinv[i - 1] * self.inv[i]) % mod
    
    def ncr(self, n: int, r: int):
        if r < 0 or n < r:
            return 0
        r = min(r, n - r)
        return self.fact[n] * self.factinv[r] % self.mod * self.factinv[n - r] % self.mod
    
    def nhr(self, n: int, r: int):
        return self.ncr(n + r - 1, r)
    
    def npr(self, n: int, r: int):
        if r < 0 or n < r:
            return 0
        return self.fact[n] * self.factinv[n - r] % self.mod


def solve():
    K = int(rl())
    S = rl().rstrip()
    MOD = 10 ** 9 + 7
    
    com = Combination(2 * 10 ** 6, MOD)
    n = len(S)
    m = n + K
    ans = 0
    for i in range(n, m + 1):
        j = m - i
        ans += com.ncr(n + K - j - 1, n - 1) * pow(25, K - j, MOD) * pow(26, j, MOD)
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

ans = 0
for i in range(s, n+1):
	ncr = fac[i-1] * pow(fac[i-s]*fac[s-1] % mod, mod-2, mod) % mod
	res = pow(26, n-i, mod)* pow(25, i-s, mod) % mod
	ans = (ans + res * ncr) % mod
print(ans)

Submission status: Accepted

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

mod = 10 ** 9 + 7
n = k + s


def _fac_inv(_n, _mod):
    _fac = [1] * (_n + 1)
    _inv = [1] * (_n + 1)
    for i in range(_n):
        _fac[i + 1] = _fac[i] * (i + 1) % _mod
    _inv[_n] = pow(_fac[_n], _mod - 2, _mod)
    for i in range(_n, 0, -1):
        _inv[i - 1] = _inv[i] * i % _mod

    return _fac, _inv


fac, inv = _fac_inv(n, mod)

n25 = [1]
n26 = [1]
for _ in range(n-s):
    n25.append((n25[-1] * 25) % mod)
    n26.append((n26[-1] * 26) % mod)

ans = 0

for i in range(s, n + 1):
    ans = (ans + fac[i-1] * inv[s-1] * inv[i-s] * n25[i-s] * n26[n-i]) % mod

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 10**9 + 7
MAX_N = 2 * 10**6 + 10

# Construct factorial table
fac = [1] + [0] * MAX_N
for i in range(1, MAX_N+1):
    fac[i] = fac[i-1] * (i) % MOD

fac_inv = [1] + [0] * MAX_N
# Femrmat's little theorem says a**(p-1) mod p == 1
# then, a * a**(p-2) mod p == 1
# it means that a**(p-2) is the inverse element
# Here, Get 1 / n! first
fac_inv[MAX_N] = pow(fac[MAX_N], MOD-2, MOD)
for i in range(MAX_N, 1, -1):
    fac_inv[i-1] = fac_inv[i] * i % MOD

def mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD

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

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

Submission status: Accepted

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

mod = 10**9+7

def fpow(x, y):
  res = 1
  while y>0:
    if y%2 == 1:
      res = (res%mod * x%mod)%mod
    x = (x%mod * x%mod)%mod
    y = y//2
  return res
MAXN = 2000005
fact = [0]*MAXN
fact[0] = 1
for i in range(1, MAXN):
  fact[i] = (i%mod * fact[i-1]%mod)%mod
  
def inv(a):
  return fpow(a, mod-2)
  
n = len(s)
ans = fpow(26, n+k)
for m in range(n):
    ncm = (fact[n+k]%mod * inv(fact[m])%mod)%mod
    ncm = (ncm%mod * inv(fact[n+k-m])%mod)%mod
    
    p = fpow(25, n+k-m)
    
    val = (ncm%mod * p%mod)%mod
    
    ans = (ans%mod - val%mod + mod)%mod
print(ans%mod)

Submission status: Accepted

Solution code:
# 解説AC
# https://kkt89.hatenablog.com/entry/2020/06/21/ABC171_F-Strivore
# で理解
MOD = 10**9 + 7


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

    def __truediv__(self, other):
        return (modint(self.value * pow(other.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(self.value * pow(other, MOD - 2, MOD)))

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

    def __rtruediv__(self, other):
        return (modint(other.value * pow(self.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(other * pow(self.value, MOD - 2, MOD)))

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))


def main():
    K = int(input())
    S = input()
    N = len(S)
    m = N+K + 5
    fac = [0] * m
    finv = [0] * m
    inv = [0] * m

    def COMBinitialize(m):
        fac[0] = 1
        finv[0] = 1
        if m > 1:
            fac[1] = 1
            finv[1] = 1
            inv[1] = 1
            for i in range(2, m):
                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

    COMBinitialize(m)
    M = K + N
    ans = modint(pow(26, M, MOD))
    for i in range(N):
        v = COMB(M, i) * pow(25, M-i, MOD)
        v %= MOD
        ans -= v
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
MOD = 10**9+7
def frac(limit):
    frac = [1]*limit
    for i in range(2,limit):
        frac[i] = i * frac[i-1]%MOD
    fraci = [None]*limit
    fraci[-1] = pow(frac[-1], MOD -2, MOD)
    for i in range(-2, -limit-1, -1):
        fraci[i] = fraci[i+1] * (limit + i + 1) % MOD
    return frac, fraci

frac, fraci = frac(2341398)
def cmb(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*fraci[b]*fraci[a-b]%MOD

K, = map(int, input().split())
t = len(input().strip())

R = 0
for x in range(K+1):
    R += cmb(K+t-x-1, t-1)*pow(25, K-x, MOD)*pow(26, x, MOD)%MOD
    R %= MOD
print(R)

Submission status: Accepted

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

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)
    # b1: bool, i4: int32, i8: int64, double: f8, [:], [:, :]
    cc.compile()
    exit()
else:
    # read parameter
    from my_module import main
    K = int(input())
    S = input()
    print(main(K, len(S)))

Submission status: Accepted

Solution code:
# 解説AC
# 解説放送と
# https://twitter.com/kyopro_friends/status/1274710268262547456?s=20
# で理解
MOD = 10**9 + 7


def main():
    K = int(input())
    S = input()
    N = len(S)
    m = N+K + 5
    fac = [0] * m
    finv = [0] * m
    inv = [0] * m

    def COMBinitialize(m):
        fac[0] = 1
        finv[0] = 1
        if m > 1:
            fac[1] = 1
            finv[1] = 1
            inv[1] = 1
            for i in range(2, m):
                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

    COMBinitialize(m)
    ans = 0
    for i in range(K+1):
        v = COMB(N-1+K-i, N-1)
        v %= MOD
        v *= pow(25, (K-i), MOD)
        v %= MOD
        v *= pow(26, i, MOD)
        v %= MOD
        ans += v
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7


def main():
    K = int(input())
    S = input()
    N = len(S)
    m = N+K + 5
    fac = [0] * m
    finv = [0] * m
    inv = [0] * m

    def COMBinitialize(m):
        fac[0] = 1
        finv[0] = 1
        if m > 1:
            fac[1] = 1
            finv[1] = 1
            inv[1] = 1
            for i in range(2, m):
                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

    COMBinitialize(m)
    ans = 0
    for i in range(K+1):
        v = COMB(N-1+K-i, N-1)
        v %= MOD
        v *= pow(25, (K-i), MOD)
        v %= MOD
        v *= pow(26, i, MOD)
        v %= MOD
        ans += v
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    class Combination:
        def __init__(self, n_max, mod=10**9+7):
            # O(n_max + log(mod))
            self.mod = mod
            f = 1
            self.fac = fac = [f]
            for i in range(1, n_max+1):
                f = f * i % mod
                fac.append(f)
            f = pow(f, mod-2, mod)
            self.facinv = facinv = [f]
            for i in range(n_max, 0, -1):
                f = f * i % mod
                facinv.append(f)
            facinv.reverse()

        # "n 要素" は区別できる n 要素
        # "k グループ" はちょうど k グループ

        def __call__(self, n, r):  # self.C と同じ
            return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

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

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

        def H(self, n, r):
            if (n == 0 and r > 0) or r < 0:
                return 0
            return self.fac[n+r-1] * self.facinv[r] % self.mod * self.facinv[n-1] % self.mod

        def rising_factorial(self, n, r):  # 上昇階乗冪 n * (n+1) * ... * (n+r-1)
            return self.fac[n+r-1] * self.facinv[n-1] % self.mod

        def stirling_first(self, n, k):  # 第 1 種スターリング数  lru_cache を使うと O(nk)  # n 要素を k 個の巡回列に分割する場合の数
            if n == k:
                return 1
            if k == 0:
                return 0
            return (self.stirling_first(n-1, k-1) + (n-1)*self.stirling_first(n-1, k)) % self.mod

        def stirling_second(self, n, k):  # 第 2 種スターリング数 O(k + log(n))  # n 要素を区別のない k グループに分割する場合の数
            if n == k:
                return 1  # n==k==0 のときのため
            return self.facinv[k] * sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

        def balls_and_boxes_3(self, n, k):  # n 要素を区別のある k グループに分割する場合の数  O(k + log(n))
            return sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

        def bernoulli(self, n):  # ベルヌーイ数  lru_cache を使うと O(n**2 * log(mod))
            if n == 0:
                return 1
            if n % 2 and n >= 3:
                return 0  # 高速化
            return (- pow(n+1, self.mod-2, self.mod) * sum(self.C(n+1, k) * self.bernoulli(k) % self.mod for k in range(n))) % self.mod

        def faulhaber(self, k, n):  # べき乗和 0^k + 1^k + ... + (n-1)^k
            # bernoulli に lru_cache を使うと O(k**2 * log(mod))  bernoulli が計算済みなら O(k * log(mod))
            return pow(k+1, self.mod-2, self.mod) * sum(self.C(k+1, j) * self.bernoulli(j) % self.mod * pow(n, k-j+1, self.mod) % self.mod for j in range(k+1)) % self.mod

        def lah(self, n, k):  # n 要素を k 個の空でない順序付き集合に分割する場合の数  O(1)
            return self.C(n-1, k-1) * self.fac[n] % self.mod * self.facinv[k] % self.mod

        def bell(self, n, k):  # n 要素を k グループ以下に分割する場合の数  O(k**2 + k*log(mod))
            return sum(self.stirling_second(n, j) for j in range(1, k+1)) % self.mod

    k = int(readline())
    s = readline().rstrip().decode()
    n = len(s)
    ans = 0
    mod = 10 ** 9 + 7
    comb = Combination(n + k)
    v = 1
    for i in range(k + 1):
        ans += comb(n + k, i) * v
        ans %= mod
        v *= 25
        v %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

U=2*10**6+1
mod=10**9+7

fact=[1]*(U+1)
fact_inv=[1]*(U+1)

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

for i in range(U,0,-1):
	fact_inv[i-1]=(fact_inv[i]*i)%mod

def comb(n,k):
    if k<0 or k>n:
        return 0
    x=fact[n]
    x*=fact_inv[k]
    x%=mod
    x*=fact_inv[n-k]
    x%=mod
    return x
m=len(s)
ans=0
for i in range(k+1):
    ans=(ans+pow(25,i,mod)*comb(m+i-1,m-1)*pow(26,k-i,mod))%mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc171/tasks/abc171_f

class Combination:                                      # 計算量は O(n_max + log(mod))
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):                     # 階乗(= n_max !)の逆元を生成
            f = f * i % mod                             # 動的計画法による階乗の高速計算
            fac.append(f)                               # fac は階乗のリスト
        f = pow(f, mod-2, mod)                          # 階乗から階乗の逆元を計算。フェルマーの小定理より、　a^-1 = a^(p-2) (mod p) if p = prime number and p and a are coprime
                                                        # python の pow 関数は自動的に mod の下での高速累乗を行ってくれる
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):                   # 上記の階乗の逆元から階乗の逆元のリストを生成（＝ facinv ）
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()


    def __call__(self, n, r):  # self.C と同じ
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def C(self, n, r):
        if not 0 <= r <= n: return 0                    # 範囲外という事はすなわち、そのような場合の数は無いはずなので、0を出力すればよい。（これが無いとREになる）
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod


K = int(input())

S = input()

l = len(S)

MOD = 10**9+7

comb = Combination(K + l + 2)

res = 0

for n in range(K+1):
    res += (comb.C(n + l - 1, l - 1) * pow(25, n, MOD) * pow(26, K-n,MOD))%MOD


print(res%MOD)

Submission status: Accepted

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

mod = 10**9 + 7

class Combination:
    def __init__(self, n):
        self.facts = [1 for i in range(n+1)]
        self.invs = [1 for i in range(n+1)]
        
        for i in range(1, n+1):
            self.facts[i] = self.facts[i-1] * i % mod
            self.invs[i] = pow(self.facts[i], mod-2, mod)

    def ncr(self, n, r):
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0
        else:
            return self.facts[n] * self.invs[r] * self.invs[n-r] % mod

    def nhr(self, n, r):
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0
        else:
            return self.ncr(n+r-1, n-1)

N = K+len(S)
pow25 = [1] * (N+1)
pow26 = [1] * (N+1)
for i in range(1, N+1):
    pow25[i] = (pow25[i-1] * 25) % mod
    pow26[i] = (pow26[i-1] * 26) % mod

comb = Combination(K+len(S))

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

print(ans)