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):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

k = I()
s = S()
l = len(s)
n = k + l + 1
fac = [1] * (n + 1)
inv = [1] * (n + 1)
twentyFive = [1] * (n + 1)
twentySix = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod
    twentyFive[j] = twentyFive[j - 1] * 25 % mod
    twentySix[j] = twentySix[j - 1] * 26 % mod


inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod


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




ans = 0
for i in range(k + 1):
    ans += comb(l - 1 + i, i) * twentyFive[i] % mod * twentySix[k - i] % mod
    ans %= mod

print(ans)

Solution (Python):

import sys
MOD = 10**9+7
K = int(input())
S = input()
l = len(S)
ans = 0

tmp = pow(26,K,MOD)
ans = tmp
waru = pow(26,-1,MOD)

for i in range(1,K+1):
    tmp = (tmp*25*waru)%MOD
    tmp = (tmp*(l-1+i)*pow(i,-1,MOD))%MOD
    ans = (ans+tmp)%MOD

print(ans)

Solution (Python):
K=int(input())
s=input()
S=len(s)
mod=10**9+7
MAX_N=10**7
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

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

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

class Combination:
    def __init__(self, size):
        self.size = size + 2

        f = 1
        self.fact = fact = [f]
        for i in range(1, size+1):
            f = f * i % MOD
            fact.append(f)
        f = pow(f, MOD-2, MOD)
        self.factInv = factInv = [f]
        for i in range(size, 0, -1):
            f = f * i % MOD
            factInv.append(f)
        factInv.reverse()

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % MOD

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % MOD) % MOD

    def nhr(self, n, r):  
        return self.ncr(n + r - 1, n - 1)

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

comb = Combination(N + K + 100)

ans = 0
L = 1
R = pow(26, K, MOD)
inv26 = pow(26, MOD - 2, MOD)
for l in range(K + 1):
    ans += L * comb.nhr(N, l) * R
    ans %= MOD

    L = L * 25 % MOD
    R = R * inv26 % MOD

print(ans)

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

class Combination:
    def __init__(self, size, MOD):
        self.size = size + 2

        f = 1
        self.fact = fact = [f]
        for i in range(1, size+1):
            f = f * i % MOD
            fact.append(f)
        f = pow(f, MOD-2, MOD)
        self.factInv = factInv = [f]
        for i in range(size, 0, -1):
            f = f * i % MOD
            factInv.append(f)
        factInv.reverse()

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % MOD

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % MOD) % MOD

    def nhr(self, n, r):  
        return self.ncr(n + r - 1, n - 1)

def sol():
    K = int(input())
    S = input()
    N = len(S)

    comb = Combination(N + K + 100, MOD)

    ans = 0
    L = 1
    R = pow(26, K, MOD)
    inv26 = pow(26, MOD - 2, MOD)
    for l in range(K + 1):
        ans += L * comb.nhr(N, l) * R
        ans %= MOD

        L = L * 25 % MOD
        R = R * inv26 % MOD

    print(ans)
sol()

Solution (Python):

import sys
MOD = 10**9 + 7
def main(K, S):
    N = len(S)
    fu = FactorialUtils(N + K)
    ans = Mint()
    for i in range(K + 1):
        tmp = Mint(1)
        tmp *= fu.multichoose(N, K - i)
        tmp *= pow(25, K - i, MOD)
        tmp *= pow(26, i, MOD)
        ans += tmp
    print(ans)

class FactorialUtils:
    def __init__(self, n):
        self.fac = [1] * (n + 1)
        self.ifac = [1] * (n + 1)
        for i in range(2, n + 1): self.fac[i] = self.fac[i - 1] * i % MOD
        self.ifac[n] = pow(self.fac[n], MOD - 2, MOD)
        for i in range(n, 1, -1): self.ifac[i - 1] = self.ifac[i] * i % MOD

    def choose(self, n, r):
        if r < 0 or r > n: return 0
        return (self.fac[n] * self.ifac[n - r] % MOD) * self.ifac[r] % MOD

    def multichoose(self, u, k):
        return (self.fac[u + k - 1] * self.ifac[u - 1] % MOD) * self.ifac[k] % MOD

class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % MOD
        return self

    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other)) % MOD
        if self.value < 0: self.value += MOD
        return self

    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj

    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self

    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self

    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj

    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj

if __name__ == '__main__':
    input = sys.stdin.readline
    K = int(input())
    S = input().rstrip()
    main(K, S)

Solution (Python):
 

from collections import defaultdict

import sys, math
f = None
try:
	f = open('q1.input', 'r')
except IOError:
	f = sys.stdin
if 'xrange' in dir(__builtins__):
	range = xrange

sys.setrecursionlimit(10**2)

	
def print_case_iterable(case_num, iterable):
	print("Case 

def print_case_number(case_num, iterable):
	print("Case 

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

def factorial(n) : 
	M = NUMBER
	f = 1
  
	for i in range(1, n + 1):  
		f = (f * i) % M 
						
	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): 
	
	cnt = 0
	
	stack = [[1,0,0,0]]
	while stack:
		v,neig_i,parent,depth = stack[-1]
		parents[v] = parent
		depths[v] = depth
		
		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
  



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
	
	for i in range(T):
		n = ri()
		s = rs()
		
		
		

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

if 'xrange' in dir(__builtins__):
	import cStringIO
	output = cStringIO.StringIO()




if __name__ == '__main__':
	main()

Solution (Python):
 

from collections import defaultdict

import sys, math
f = None
try:
	f = open('q1.input', 'r')
except IOError:
	f = sys.stdin
if 'xrange' in dir(__builtins__):
	range = xrange

sys.setrecursionlimit(10**2)

	
def print_case_iterable(case_num, iterable):
	print("Case 

def print_case_number(case_num, iterable):
	print("Case 

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

def factorial(n) : 
	M = NUMBER
	f = 1
  
	for i in range(1, n + 1):  
		f = (f * i) % M 
						
	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): 
	
	cnt = 0
	
	stack = [[1,0,0,0]]
	while stack:
		v,neig_i,parent,depth = stack[-1]
		parents[v] = parent
		depths[v] = depth
		
		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
  



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 = [0]*(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 + 1
	
def main():
	T = 1
	
	for i in range(T):
		n = ri()
		s = rs()
		
		
		

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

if 'xrange' in dir(__builtins__):
	import cStringIO
	output = cStringIO.StringIO()




if __name__ == '__main__':
	main()

Solution (Python):


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


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

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

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

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

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

Solution (Python):
MOD = 10 ** 9 + 7
K = int(input())
M = len(input())
N = M + K
 
pow25 = [1] * (N + 1)
fac = [1] * (N + 1)
inv = [1] * (N + 1)
for x in range(1, N + 1):
    fac[x] = fac[x - 1] * x % MOD
    pow25[x] = pow25[x - 1] * 25 % MOD
inv[N] = pow(fac[N], MOD-2, MOD)
for x in range(N - 1, -1, -1):
    inv[x] = inv[x + 1] * (x + 1) % MOD
 
def binom(n, k):
    return fac[n] * inv[n - k] % MOD * inv[k] % MOD
 
ans = 0
for k in range(M, N + 1):
    ans += binom(N, k) * pow25[N - k] % MOD
    ans %= MOD
print(ans)

Solution (Python):

import sys
input = sys.stdin.readline
MOD = 10**9 + 7
MAX_N = 2 * 10**6 + 10


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




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)

Solution (Python):
class ModCombination:
    """
    nCk (mod m)を扱うクラス
    """

    def __init__(self, mod, n_max):
        """
        イニシャライザ
        予め 1~nの階乗と階乗の逆元を計算しておく
        :param mod: 法
        :param n_max: nの最大値(100,000で約1秒)
        """
        self.mod = mod
        self.n_max = n_max
        self.facts = [1, 1]
        self.inverses = [None, 1]
        self.fact_inverses = [1, 1]

        for i in range(2, self.n_max + 1):
            self.facts.append(self.facts[i - 1] * i % self.mod)
            
            self.inverses.append(
                self.mod - self.inverses[self.mod % i] *
                (self.mod // i) % self.mod
            )
            self.fact_inverses.append(
                self.fact_inverses[i - 1] * self.inverses[i] % self.mod
            )

    def mod_combination(self, n, k):
        """
        nCk (mod m)を計算する
        :param n: n
        :param k: k
        :return: nCk (mod m)
        """
        if k > n:
            raise ValueError
        elif k == n:
            return 1
        elif k == 0:
            return 1

        denominator = self.fact_inverses[k] * self.fact_inverses[n - k] % self.mod
        return self.facts[n] * denominator % self.mod


def mod_pow(a, n, mod):
    """
    二分累乗法による a^n (mod m)の実装
    :param a: 累乗の底
    :param n: 累乗の指数
    :param mod: 法
    :return: a^n (mod m)
    """

    result = 1
    a_n = a
    while n > 0:
        if n & 1:
            result = result * a_n % mod
        a_n = a_n * a_n % mod
        n >>= 1
    return result


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

n = len(S)

comb = ModCombination(mod=MOD, n_max=n + K)

ans = 0
for i in range(K + 1):
    ans += (mod_pow(25, i, MOD) * comb.mod_combination(i + n - 1, n - 1)) % MOD * mod_pow(26, K - i, MOD)
    ans %= MOD

print(ans)

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

Solution (Python):



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

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

Solution (Python):


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

Solution (Python):




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

Solution (Python):
k = int(input())
s = input()
p = 1000000007
x = 0
inv = [0, 1]
fact = [1, 1]
factinv = [1, 1]
for i in range(2, k+len(s)+1):
    inv.append(-inv[p%i]*(p//i)%p)
    fact.append(fact[-1]*i%p)
    factinv.append(factinv[-1]*inv[-1]%p)
def cmb(n, r, p):
    return fact[n]*factinv[r]*factinv[n-r]%p
a = [1]
b = [1]
for _ in range(k):
    a.append(a[-1]*25%p)
    b.append(b[-1]*26%p)
for i in range(k+1):
    x = (x+a[i]*b[k-i]*cmb(i+len(s)-1, i, p))%p
print(x)

Solution (Python):
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[n] = pow(self.facts[n], mod-2, mod)
        for i in range(1, n+1):
            self.invs[n-i] = self.invs[n-i+1] * (n-i+1) % 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)