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: Time Limit Exceeded

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):
	summ = 0
	k = len(s)
	n = n+k
	d = 26
	for j in range(n-k+1):
		summ=plus(summ,mult(choose(n,j+k),pow(d-1,n-k-j)))
		# summ=mult(summ,)
	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: Time Limit Exceeded

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 = n+k
    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 )

    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: Time Limit Exceeded

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

    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: Time Limit Exceeded

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

    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):
        ans += power(25, i, mod)*cmb1(i+n-1, n-1, mod)*power(26, k-i, mod)
    print(ans%mod)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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):
    ans += power(25, i, mod)*cmb1(i+n-1, n-1, mod)*power(26, k-i, mod)
print(ans%mod)

Submission status: Time Limit Exceeded

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

mod = 10 ** 9 + 7
s = len(s)
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):
    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: Time Limit Exceeded

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

mod = 10 ** 9 + 7
s = len(s)
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):
    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: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from numba import njit

K = int(sys.stdin.readline().rstrip())
S = sys.stdin.readline().rstrip()
M = int(10**9 + 7)

@njit
def fast_pow(a, b, m):
    base = a
    res = 1
    while b:
        if b & 1:
            res = res * base % m
        base = base * base % m
        b //= 2
    return res

@njit
def build_factorial(max_value):
    fact = [1]
    for i in range(1, max_value + 1):
        fact.append(fact[-1] * i % M)

    finv = [fast_pow(fact[-1], M - 2, M)]
    for i in range(max_value, 0, -1):
        finv.append(finv[-1] * i % M)
    finv.reverse()

    return fact, finv

fact, finv = build_factorial(K + len(S) + 10)

def comb(a, b, m):
    return fact[a] * finv[b] % m * finv[a - b] % m

def hcomb(a, b, m):
    return comb(a + b - 1, a - 1, m)

ans = 0
for l in range(0, K + 1):
    ans += pow(26, l, M) * pow(25, K - l, M) % M * hcomb(len(S), K - l, M) % M
    ans %= M
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys

K = int(sys.stdin.readline().rstrip())
S = sys.stdin.readline().rstrip()
M = int(10**9 + 7)

fact = [1]
for i in range(1, K + len(S) + 10):
    fact.append(fact[-1] * i % M)

finv = [pow(fact[-1], M - 2, M)]
for i in range(K + len(S) + 9, 0, -1):
    finv.append(finv[-1] * i % M)
finv.reverse()

def comb(a, b, m):
    return fact[a] * finv[b] % m * finv[a - b] % m

def hcomb(a, b, m):
    return comb(a + b - 1, a - 1, m)

ans = 0
for l in range(0, K + 1):
    ans += pow(26, l, M) * pow(25, K - l, M) % M * hcomb(len(S), K - l, M) % M
    ans %= M
print(ans)

Submission status: Time Limit Exceeded

Solution code:
K = int(input())
S = input()
M = int(10**9 + 7)

fact = [1]
for i in range(1, K + len(S) + 10):
    fact.append(fact[-1] * i % M)

finv = [pow(fact[-1], M - 2, M)]
for i in range(K + len(S) + 9, 0, -1):
    finv.append(finv[-1] * i % M)
finv.reverse()

def comb(a, b, m):
    return fact[a] * finv[b] % m * finv[a - b] % m

def hcomb(a, b, m):
    return comb(a + b - 1, a - 1, m)

ans = 0
for l in range(0, K + 1):
    ans += pow(26, l, M) * pow(25, K - l, M) % M * hcomb(len(S), K - l, M) % M
    ans %= M
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7

def binomial_coefficients(n, k, mod):
  ans = 1
  for i in range(k):
    ans *= (n-i)%mod
    ans *= pow(i+1, mod-2 , mod)
    ans %= mod
  return ans

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def fast_pow(a, b, m):
    base = a
    res = 1
    while b:
        if b & 1:
            res = res * base % m
        base = base * base % m
        b //= 2
    return res

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

fact = [1]
for i in range(1, K + len(S) + 10):
    fact.append(fact[-1] * i % M)
inv = [fast_pow(f, M - 2, M) for f in fact]

def comb(a, b, m):
    return fact[a] * inv[b] % m * inv[a - b] % m

def hcomb(a, b, m):
    return comb(a + b - 1, a - 1, m)

ans = 0
for l in range(0, K + 1):
    ans += fast_pow(26, l, M) * fast_pow(25, K - l, M) % M * hcomb(len(S), K - l, M) % M
    ans %= M
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# K = 37564
# S = "whydidyoudesertme"
# K = 5
# S = "oof"
K = int(input())
S = input()

P = 10 ** 9 + 7
N = len(S)

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

    INV[i] = P - INV[P % i] * (P // i) % 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
    )
print(ret % P)

Submission status: Time Limit Exceeded

Solution code:
# K = 37564
# S = "whydidyoudesertme"
# K = 5
# S = "oof"
K = int(input())
S = input()

P = 10 ** 9 + 7
N = len(S)

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

    INV[i] = P - INV[P % i] * (P // i) % P
    invf *= INV[i]
    invf %= P
    INVF[i] = invf


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


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

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7

def binomial_coefficients(n, k, mod):
  ans = 1
  for i in range(k):
    ans *= (n-i)%mod
    ans *= pow(i+1, -1 , mod)
    ans %= mod
  return ans

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

Submission status: Time Limit Exceeded

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)
    for i in range(k + 1):
        ans += comb(n + k, i) * pow(25, i, mod)
        ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def choose(n,a,mod):
    x, y = 1, 1
    for i in range(a):
        x = x * (n - i) % mod
        y = y * (i + 1) % mod
    return x * pow(y, mod - 2, mod) % mod

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

Submission status: Time Limit Exceeded

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

s = 0
for i in range(K+1):
    com = (math.factorial(len(S)-1+K-i))//(math.factorial(K-i) * math.factorial(len(S)-1))
    com7 = com%7
    s += 25**(K-i) * 26**i * com
print(s%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
k=int(input())
s=input()
ans=0
mod=1000000007
x=2200000
fact=[0]*x
invfact=[0]*x
fact[0]=1
for i in range(1,x):
    fact[i]=fact[i-1]*i%mod
invfact[x-1]=pow(fact[x-1],mod-2,mod)
for i in range(x-2,-1,-1):
    invfact[i]=invfact[i+1]*(i+1)%mod
def nCk(n,k):
    return(fact[n]*invfact[k]*invfact[n-k])%mod
for i in range(0,k+1):
    # print(nCk(len(s)+i-1,i),pow(25,i,mod),pow(26,k-i,mod))
    ans+=nCk(len(s)+i-1,i)*pow(25,i,mod)*pow(26,k-i,mod)
print(ans%mod)

Submission status: Time Limit Exceeded

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

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

def comb(n, k):
    return fact[n] * invfact[k] * invfact[n-k] % MOD

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

Submission status: Time Limit Exceeded

Solution code:
from scipy import special

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

ans = 0
for i in range(K + 1):
	a = 25 ** i * special.comb(i + SS - 1,  SS - 1, True) * 26 ** (K - i)
	ans += a
print(ans % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

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

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

ans = 0
po = 1
poo = pow(26, K, mod)
for i in range(K+1):
    ans = (ans + po * poo % mod * nCr(i+M-1, i)) % mod
    po = po * 25 % mod
    poo = poo * inv26 % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MAXN = 2*10**6+2
p = 10**9 + 7

fact = [1] * MAXN
invfact = [1] * MAXN
for i in range(1, MAXN):
    fact[i] = fact[i-1] * i % p
invfact[MAXN-1] = pow(fact[MAXN-1], p-2, p)
for i in range(MAXN-1, 0, -1):
    invfact[i-1] = invfact[i] * i % p
    
def nCk(n, k):
    return fact[n] * invfact[n-k] * invfact[k] % p

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

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

Submission status: Time Limit Exceeded

Solution code:
def C(n, r):
    global MOD
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % MOD
    

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

MOD = 10 ** 9 + 7
ans = 0

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

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

Submission status: Time Limit Exceeded

Solution code:
class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def nCr(self, n, r):
        r = min(n - r, r)
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod

    def nHr(self, n, r):
        return self.nCr(n - 1 + r, r)


class PowPreCalc:
    def __init__(self, *, b, m, mod):
        """(b**m)%mod"""
        res = [1]
        t = 1
        for _ in range(m):
            t = t * b % mod
            res.append(t)
        self._res = res

    def get_pow(self, m):
        """(b**m)%mod"""
        return self._res[m]


def main():
    MOD = 10 ** 9 + 7

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

    N = len(S)

    calc = Calc(max_value=N - 1 + K, mod=MOD)

    p26 = PowPreCalc(b=26, m=K, mod=MOD)
    p25 = PowPreCalc(b=25, m=K, mod=MOD)

    ans = 0
    for tail_len in range(K + 1):
        ans = (ans
               + calc.nCr(N - 1 + K - tail_len, N - 1) * p26.get_pow(tail_len) * p25.get_pow(K - tail_len)
               ) % MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
s = input()
n = len(s)
#nCk(mod p)を求める
def comb(n, k, p):
    if n<0 or k<0 or n<k:
        return 0
    if n==0 or k==0:
        return 1
    a, b, c = 1, 1, 1
    for i in range(1, n+1):
        a = (a*i)%p
    for i in range(1, k+1):
        b = (b*i)%p
    for i in range(1, n-k+1):
        c = (c*i)%p
    return a*pow(b, p-2, p)*pow(c, p-2, p)%p
mod = 10**9+7
ans = 0
for i in range(k+1):
    pls = pow(25, i, mod)
    pls *= pow(26,k-i, mod)
    pls %= mod
    pls *= comb(i+n-1, i, mod)
    ans += pls
    ans %= mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
s = input()
n = len(s)
#nCk(mod p)を求める
def comb(n, k, p):
    if n<0 or k<0 or n<k:
        return 0
    if n==0 or k==0:
        return 1
    a, b, c = 1, 1, 1
    for i in range(1, n+1):
        a = (a*i)%p
    for i in range(1, k+1):
        b = (b*i)%p
    for i in range(1, n-k+1):
        c = (c*i)%p
    return a*pow(b, p-2, p)*pow(c, p-2, p)%p
mod = 10**9+7
ans = 0
for i in range(k+1):
    pls = pow(25, i, mod)
    pls *= pow(26,k-i, mod)
    pls *= comb(i+n-1, i, mod)
    ans += pls
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r, p):
  if (r < 0) or (n < r):
    return 0
  r = min(r, n - r)
  return fac[n] * finv[r] * finv[n-r] % p

N = 2*pow(10,6)+100
MOD = pow(10,9)+7

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


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

ans = 0
for i in range(K+1):#後ろが0個からK個まで
  factor = pow(25,K-i,MOD)*pow(26,i,MOD)%MOD
  ans = (ans + factor*cmb(s+K-i-1,s-1,MOD))%MOD

ans = ans %MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:

K=int(input())
S=input()
M=len(S)
N=K+M
mod=10**9+7
ans=pow(26,N,mod)
class Data():
    def __init__(self):
        self.power=1
        self.rev=1     
class Combi():
    def __init__(self,N,mod):
        self.lists=[Data() for _ in range(N+1)]
        self.mod=mod  
        for i in range(2,N+1):
            self.lists[i].power=((self.lists[i-1].power)*i)%self.mod
        self.lists[N].rev=pow(self.lists[N].power,self.mod-2,self.mod)
        for j in range(N,0,-1):
            self.lists[j-1].rev=((self.lists[j].rev)*j)%self.mod

    def combi(self,K,R):
        if K<R:
            return 0
        else:
            return ((self.lists[K].power)*(self.lists[K-R].rev)*(self.lists[R].rev))%self.mod
        
c=Combi(N,mod)
for i in range(M):
    ans-=c.combi(N,i)*pow(25,N-i,mod)
    ans%=mod
print(ans)