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:
class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 10 ** 6 + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 10 ** 6:
            return self.cmbl(n, r)
        return self.cmbr(n, r)

    def cmbr(self, n, r):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def main():
    K = int(input())
    S = input()
    l = len(S)
    mod = 10**9 + 7
    c = cmbs(mod)
    r = 0
    x25 = 1
    x26 = pow(26, K, mod)
    inv26 = pow(26, mod-2, mod)
    
    for i in range(K+1):
        r += c.cmb(l+i-1, i) * x25 * x26
        x25 *= 25
        x25 %= mod
        x26 *= inv26
        x26 %= mod
        r %= mod
    return r
print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys

def input():
    return sys.stdin.readline().strip()

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

    mod = 10 ** 9 + 7
    n = len(S)
    ans = 0

    def nCr(n,r):
        if n - r > r:
            return nCr(n,n-r)
        else:
            a = b = 1
            for i in range(r):
                a = (a * (n - i)) % mod
                b = (b * (r - i)) % mod
            return (a * pow(b,mod-2,mod)) % mod

    for i in range(K+1):
        ans += ((25 ** i * nCr(i+n-1,n-1)) * (26 ** (K - i))) % mod
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 10 ** 6 + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 10 ** 6:
            return self.cmbl(n, r)
        return self.cmbr(n, r)

    def cmbr(self, n, r):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def main():
    K = int(input())
    S = input()
    l = len(S)
    mod = 10**9 + 7
    c = cmbs(mod)
    r = 0
    for i in range(K+1):
        r += c.cmb(l+i-1, i) * pow(25, i, mod) * pow(26, K-i, mod)
        r %= mod
    return r
print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

mod = 10**9+7

def choose(n,r):
    p,q = 1,1
    for i in range(r):
        p = p*(n-i)%mod
        q = q*(i+1)%mod
    return p * pow(q,mod-2,mod) % mod # modの世界では逆元はpow(x,mod-2)をかけることと同じ

n = len(s)

ans = 0

for i in range(k+1):
    now = 26**(k-i) % mod
    now *= 25**i % mod
    now *= choose(i+n-1, n-1) % mod
    ans += now % mod

print(ans%mod)

Submission status: Time Limit Exceeded

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

mod = 10 ** 9 + 7
n = len(S)
ans = 0

def nCr(n,r):
    if n - r > r:
        return nCr(n,n-r)
    else:
        a = b = 1
        for i in range(r):
            a = (a * (n - i)) % mod
            b = (b * (r - i)) % mod
        return (a * pow(b,mod-2,mod)) % mod

for i in range(K+1):
    ans += ((25 ** i * nCr(i+n-1,n-1)) * (26 ** (K - i))) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
	mod=10**9+7
	k=int(input())
	s=input()
	n=len(s)
	fac=[1]
	for i in range(k+n+1):
		fac.append(fac[-1]*(i+1)%mod)
	def c(x,y):
		r=fac[y]*fac[x-y]%mod
		return fac[x]*pow(r,mod-2,mod)%mod
	ans=0
	for i in range(n,k+n+1):#iはSnの位置
		r=c(i-1,n-1)*pow(25,i-n,mod)*pow(26,n+k-i,mod)%mod
		ans+=r
		ans%=mod
	print(ans)
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

# コンビネーション、さらに高速。あらかじめO(N)の計算をすることでのちの計算が早くなる
def cmb(n,r,mod):
  if (r<0 or r>n):
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod
g1=[1,1] 
g2=[1,1] 
inverse=[0,1]
for i in range(2,n+k+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)

import numpy as np
tmp=[pow(25,i,mod)*cmb(i+n-1,n-1,mod) for i in range(k+1)]
f=np.array(tmp)
g=np.zeros(k+1,int)
g[0]=1
for ki in range(1,k+1):
  g[ki]=f[ki]+26*g[ki-1]
  g[ki]%=mod
print(g[k])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
#from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
#import numba

def run():
    K = int(input())
    S = input()
    L = len(S)
    mod = 10 ** 9 +7
    def comb_mod2(n, a, mod):
        """
        return: [n, a] % mod
        Note: mod must be a prime number
        """
        if a == 0:
            return 1 % mod
        ret = 1
        for i in range(1, a + 1):
            ret *= n - i + 1
            ret %= mod
            ret *= inv[i]
            ret %= mod
        return ret

    ##################################################################
    def generate_inv(n, mod):
        """
        逆元行列
        n >= 2
        Note: mod must bwe a prime number
        """
        ret = [0, 1]
        for i in range(2, n + 1):
            next = -ret[mod % i] * (mod // i)
            next %= mod
            ret.append(next)
        return ret

    inv = generate_inv(10 ** 6, mod)

    ret = 0
    tmp_comb = 1

    pow25 = [pow(25, i, mod) for i in range(L+K)]
    pow26 = [pow(26, i, mod) for i in range(L + K)]
    for k in range(L, L+K+1):
        if k == L:
            tmp_comb = 1
        else:
            tmp_comb *= k-1
            tmp_comb %= mod
            tmp_comb *= inv[k-L]
            tmp_comb %= mod
        pow25_tmp = pow25[k-L]
        pow26_tmp = pow26[L+K-k]
        tmp_ret = pow25_tmp * pow26_tmp
        tmp_ret %= mod
        tmp_ret *= tmp_comb
        tmp_ret %= mod
        ret += tmp_ret
        ret %= mod
    print(ret)



if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
K=int(input())
S=input()
N=len(S)
mod=10**9+7

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

def comb(n,r):
    ret=fact[n]*pow(fact[r],-1,mod)*pow(fact[n-r],-1,mod)%mod
    return ret

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
K = int(input())
S = input()
n = len(S)
MOD = 10 ** 9 + 7
MAX = 2 * 10 ** 6 + 5

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

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

A = 0
for i in range(K + 1):
    A1 = (26 ** (K - i)) % MOD
    A2 = (((25 ** i) % MOD) * nCk(i + n - 1, n - 1)) % MOD
    A += (A1 * A2) % MOD
    A %= MOD

print(A % MOD)

Submission status: Time Limit Exceeded

Solution code:
def modCom(n, k, mod):
    p, q = 1, 1
    for i in range(n-k+1, n+1):
        p = (p * i) % mod
    for i in range(2, k+1):
        q = (q * i) % mod
    return p * pow(q, mod-2, mod) % mod

mod = 10**9+7
K = int(input())
S = input()
L = len(S)
ans = 0
for i in range(K+1):
    ans += modCom(K-i+L-1, L-1, mod) * pow(25, K-i, mod) * pow(26, i, mod)
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:

def resolve():
    def COMinit(n, MOD):
        fact = [1, 1]
        fact_inv = [1, 1]
        inv = [0, 1]
        for i in range(2, n + 1):
            fact.append((fact[-1] * i) % MOD)
            inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
            fact_inv.append((fact_inv[-1] * inv[i]) % MOD)
        return fact, fact_inv

    # 二項係数計算
    def Combination(n, k, MOD=10 ** 9 + 7):
        # fac, finv = COMinit(n, MOD)
        if n < k: return 0
        if n < 0 or k < 0: return 0
        ret = fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
        return ret

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

    fac, finv = COMinit(N + K, MOD)
    pow25 = 1
    pow26 = pow(26, K, MOD)
    inv26 = pow(26, MOD - 2, MOD)
    ans = 0
    for i in range(K + 1):
        ans += pow25 * Combination(N - 1 + i, N - 1) * pow26
        ans %= MOD
        pow25 = pow25 * 25 % MOD
        pow26 = pow26 * inv26 % MOD

    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

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


def framod(n, mod, a=1):
    for i in range(1, n+1):
        a = a * i % mod
    return a


def power(n, r, mod):
    if r == 0:
        return 1
    if r % 2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r % 2 == 1:
        return n * power(n, r-1, mod) % mod


def comb(n, k, mod):
    a = framod(n, mod)
    b = framod(k, mod)
    c = framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod


com = [1]*k
# or i in range(k+1):
#comb[i+1] = comb

a25 = [1]*(k+1)
for i in range(k):
    a25[i+1] = a25[i]*25 % mod
a26 = [1]*(k+1)
for i in range(k):
    a26[i+1] = a26[i]*26 % mod
num = 0
for i in range(0, k+1):
    num = (num+comb(i+n-1, n-1, mod)*a25[i] % mod * a26[k-i]) % mod
print(num)

Submission status: Time Limit Exceeded

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

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


def framod(n, mod, a=1):
    for i in range(1, n+1):
        a = a * i % mod
    return a


def power(n, r, mod):
    if r == 0:
        return 1
    if r % 2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r % 2 == 1:
        return n * power(n, r-1, mod) % mod


def comb(n, k, mod):
    a = framod(n, mod)
    b = framod(k, mod)
    c = framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod


a25 = [1]*(k+1)
for i in range(k):
    a25[i+1] = a25[i]*25 % mod
a26 = [1]*(k+1)
for i in range(k):
    a26[i+1] = a26[i]*26 % mod
num = 0
for i in range(0, k+1):
    num = num+comb(i+n-1, n-1, mod)*a25[i] % mod * a26[k-i] % mod
print(num)

Submission status: Time Limit Exceeded

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

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


def framod(n, mod, a=1):
    for i in range(1, n+1):
        a = a * i % mod
    return a


def power(n, r, mod):
    if r == 0:
        return 1
    if r % 2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r % 2 == 1:
        return n * power(n, r-1, mod) % mod


def comb(n, k, mod):
    a = framod(n, mod)
    b = framod(k, mod)
    c = framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod


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

Submission status: Time Limit Exceeded

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

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


def framod(n, mod, a=1):
    for i in range(1, n+1):
        a = a * i % mod
    return a


def power(n, r, mod):
    if r == 0:
        return 1
    if r % 2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r % 2 == 1:
        return n * power(n, r-1, mod) % mod


def comb(n, k, mod):
    a = framod(n, mod)
    b = framod(k, mod)
    c = framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod


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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()

def resolve():
    MOD = 10 ** 9 + 7
    def COMinit(n, MOD):
        fact = [1, 1]
        fact_inv = [1, 1]
        inv = [0, 1]
        for i in range(2, n + 1):
            fact.append((fact[-1] * i) % MOD)
            inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
            fact_inv.append((fact_inv[-1] * inv[i]) % MOD)
        return fact, fact_inv

    # 二項係数計算
    def Combination(n, k, MOD=10 ** 9 + 7):
        # fac, finv = COMinit(n, MOD)
        if n < k: return 0
        if n < 0 or k < 0: return 0
        ret = fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
        return ret

    K = int(inp())
    S = inpS()
    N = len(S)

    fac, finv = COMinit(N + K, MOD)
    v = 1
    ans = 0
    for i in range(K + 1):
        ans += Combination(N + K, i) * v
        ans %= MOD
        v *= 25
        v %= MOD
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:

def resolve():
    MOD = 10 ** 9 + 7
    def COMinit(n, MOD):
        fact = [1, 1]
        fact_inv = [1, 1]
        inv = [0, 1]
        for i in range(2, n + 1):
            fact.append((fact[-1] * i) % MOD)
            inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
            fact_inv.append((fact_inv[-1] * inv[i]) % MOD)
        return fact, fact_inv

    # 二項係数計算
    def Combination(n, k, MOD=10 ** 9 + 7):
        # fac, finv = COMinit(n, MOD)
        if n < k: return 0
        if n < 0 or k < 0: return 0
        ret = fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
        return ret

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

    fac, finv = COMinit(N + K, MOD)
    v = 1
    ans = 0
    for i in range(K + 1):
        ans += Combination(N + K, i) * v
        ans %= MOD
        v *= 25
        v %= MOD
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r, mod):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod
mod = 10**9 + 7
fact = [1, 1]
factinv = [1, 1]
inv = [0,1]

k = int(input())
s = input()
t = len(s)
n = k + t
for i in range(2,n+1):
    fact.append((fact[-1] * i) % mod)
    inv.append((inv[mod % i] * (mod - (mod // i))) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)
ans = 0
for i in range(k+1):
    ans += (cmb(k-i+t-1,t-1,mod)*pow(25,k-i,mod)*pow(26,i,mod))%mod
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
s = input()
mod = 10**9+7
maxn = 2000005
fact = [0 for i in range(maxn)]
fact[0] = 1
for i in range(1,maxn):
	fact[i] = (i*fact[i-1])%mod
n = len(s)
ans = pow(26,n+k,mod)
for m in range(n):
	calc = (fact[n+k]%mod * pow(fact[m],mod-2,mod))%mod
	calc = (calc * pow(fact[n+k-m],mod-2,mod))%mod
	p = pow(25,n+k-m,mod)
	val = (calc*p)%mod
	ans = (ans-val)%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6 + 7
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6 + 7
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6 + 7
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**7
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**9
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007
fact = []
fact_inv = []
pow_ = []
pow25_ = []
pow26_ = []

def pow_ini(nn):
	global pow_
	pow_.append(nn)
	for j in range(62):
		nxt = pow_[j] * pow_[j]
		nxt %= mod
		pow_.append(nxt)
	return

def pow_ini25(nn):
	global pow25_
	pow25_.append(nn)
	for j in range(62):
		nxt = pow25_[j] * pow25_[j]
		nxt %= mod
		pow25_.append(nxt)
	return

def pow_ini26(nn):
	global pow26_
	pow26_.append(nn)
	for j in range(62):
		nxt = pow26_[j] * pow26_[j]
		nxt %= mod
		pow26_.append(nxt)
	return

def pow1(k):
	ansk = 1
	for ntmp in range(62):
		if((k >> ntmp) % 2 == 1):
			ansk *= pow_[ntmp]
			ansk %= mod
	return ansk

def pow25(k):
	ansk = 1
	for ntmp in range(62):
		if((k >> ntmp) % 2 == 1):
			ansk *= pow25_[ntmp]
			ansk %= mod
	return ansk

def pow26(k):
	ansk = 1
	for ntmp in range(62):
		if((k >> ntmp) % 2 == 1):
			ansk *= pow26_[ntmp]
			ansk %= mod
	return ansk

def fact_ini(n):
	global fact
	global fact_inv
	global pow_
	for i in range(n + 1):
		fact.append(0)
		fact_inv.append(0)
	fact[0] = 1
	for i in range(1, n + 1, 1):
		fact_tmp = fact[i - 1] * i
		fact_tmp %= mod
		fact[i] = fact_tmp
	pow_ini(fact[n])
	fact_inv[n] = pow1(mod - 2)
	for i in range(n - 1, -1, -1):
		fact_inv[i] = fact_inv[i + 1] * (i + 1)
		fact_inv[i] %= mod
	return

def nCm(n, m):
	assert(m >= 0)
	assert(n >= m)
	ans = fact[n] * fact_inv[m]
	ans %= mod
	ans *= fact_inv[n - m]
	ans %= mod
	return ans;

fact_ini(2200000)
pow_ini25(25)
pow_ini26(26)
K = int(input())
S = input()
N = len(S)
ans = 0
for k in range(0, K+1, 1):
	n = N + K - k
	anstmp = 1
	anstmp *= pow26(k)
	anstmp %= mod
	anstmp *= nCm(n - 1, N - 1)
	anstmp %= mod
	anstmp *= pow25(n - N)
	anstmp %= mod
	ans += anstmp
	ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007
fact = []
fact_inv = []
pow_ = []

def pow_ini(nn):
	pow_ = []
	pow_.append(nn)
	for j in range(62):
		nxt = pow_[j] * pow_[j]
		nxt %= mod
		pow_.append(nxt)
	return pow_

def pow1(k):
	global pow_
	ansk = 1
	for ntmp in range(62):
		if((k >> ntmp) % 2 == 1):
			ansk *= pow_[ntmp]
			ansk %= mod
	return ansk

def pow25(k):
	global pow25_
	ansk = 1
	for ntmp in range(62):
		if((k >> ntmp) % 2 == 1):
			ansk *= pow25_[ntmp]
			ansk %= mod
	return ansk

def pow26(k):
	global pow26_
	ansk = 1
	for ntmp in range(62):
		if((k >> ntmp) % 2 == 1):
			ansk *= pow26_[ntmp]
			ansk %= mod
	return ansk

def fact_ini(n):
	global fact
	global fact_inv
	global pow_
	for i in range(n + 1):
		fact.append(0)
		fact_inv.append(0)
	fact[0] = 1
	for i in range(1, n + 1, 1):
		fact_tmp = fact[i - 1] * i
		fact_tmp %= mod
		fact[i] = fact_tmp
	pow_ = pow_ini(fact[n])
	fact_inv[n] = pow1(mod - 2)
	for i in range(n - 1, -1, -1):
		fact_inv[i] = fact_inv[i + 1] * (i + 1)
		fact_inv[i] %= mod
	return

def nCm(n, m):
	assert(m >= 0)
	assert(n >= m)
	ans = fact[n] * fact_inv[m]
	ans %= mod
	ans *= fact_inv[n - m]
	ans %= mod
	return ans;

fact_ini(2200000)
pow25_ = pow_ini(25)
pow26_ = pow_ini(26)
K = int(input())
S = input()
N = len(S)
ans = 0
for k in range(0, K+1, 1):
	n = N + K - k
	anstmp = 1
	anstmp *= pow26(k)
	anstmp %= mod
	anstmp *= nCm(n - 1, N - 1)
	anstmp %= mod
	anstmp *= pow25(n - N)
	anstmp %= mod
	ans += anstmp
	ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
mod = pow(10, 9) + 7
K = int(input())
S = input()
n = len(S)
ans = 0
for i in range(K+1):
    ans += comb(i+n-1, n-1) * pow(25, i) * pow(26, (K-i))
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
mod = 10**9 + 7
K = int(input())
S = input()
n = len(S)
ans = 0
for i in range(K+1):
    ans += comb(i+n-1, n-1) * 25**i * 26**(K-i)
print(ans%mod)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

# 逆元を利用してcomb(nCk)をO(1)計算
# https://qiita.com/ophhdn/items/5622ac22cce8fc9432bf
n = N + K + 3
fac = [1] * (n + 1) 
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = (fac[j - 1] * j) % 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):
  p = comb(N + K - i - 1, N - 1) * pow(26, i, MOD) * pow(25, K - i, MOD) % MOD
  ans += p
  ans %= MOD
  
print(ans)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

# 逆元を利用してcomb(nCk)をO(1)計算
# https://qiita.com/ophhdn/items/5622ac22cce8fc9432bf
n = N + K + 3
fac = [1] * (n + 1) 
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = (fac[j - 1] * j) % 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):
  p = comb(N + K - i - 1, N - 1) * (26 ** i) * (25 ** (K - i)) % MOD
  ans += p
  ans %= MOD
  
print(ans)

Submission status: Time Limit Exceeded

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

n = len(S)

def fact(n):
    res = 1
    for i in range(1, n+1):
        res *= i
    return res

def nPr(n, r):
    res = 1
    for i in range(n-r+1, n+1):
        res *= i
    return res

def nCr(n, r):
    r = min(n-r, r)
    return nPr(n, r) // fact(r)

mod = 10**9 + 7

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

    now *= nCr(n+i-1, n-1)
    ans += now
    ans %= mod
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from scipy.special import comb, perm

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

n = len(S)

mod = 10**9 + 7

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

    now *= comb(n+i-1, n-1, True)
    ans += now
    ans %= mod
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def comb(n,k,mod):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k=min(n-k,k)
    ans=1
    inv=[1]*(k+1)
    if k>=1:
        ans*=(n-k+1)%mod
    for i in range(2,k+1):
        inv[i]=mod-inv[mod%i]*(mod//i)%mod
        ans=ans*(n-k+i)*inv[i]%mod
    return ans

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

MOD = 10 ** 9 + 7

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

Submission status: Time Limit Exceeded

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

K = int(readline())
S = readline().rstrip()
N = len(S)

DIV = 10 ** 9 + 7

from functools import reduce
def nCr(n,r,DIV):
  if r<n-r:
    r=n-r
  if r==0:
    return 1
  f=lambda x,y:x*y%DIV
  X=reduce(f,range(n-r+1,n+1))
  Y=reduce(f,range(1,r+1))
  return X*pow(Y,DIV-2,DIV)%DIV

# N = |S|とする
# N + Kの長さの文字列で、N～N + K文字までが固定で、あとは任意の25文字
# の数が答え
ans = 0
for i in range(N,N + K + 1):
  # N + K文字からi文字を選ぶ場合の数
  pat = nCr(N + K, i ,DIV)
  
  # 残りN + K - i文字に対して25通り選べる場合の数
  pat *= pow(25, N + K - i, DIV)
  pat %= DIV
  ans += pat
  ans %= DIV
print(ans)

Submission status: Time Limit Exceeded

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

#output
# (o以外) o (o以外) o (f以外) f (何でも)

#こちらもmodで割った余り。maxが決まっていて、大きくない時はこちらが早い。
mod = pow(10, 9) + 7

n_ = 4 * pow(10, 6) + 1
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 cmb(n,r):
    if n <= 0 or r < 0 or r > n: return 0
    return fun[n] * rev[r] % mod * rev[n-r] % mod

#重複組み合わせはH(n, r) = cmb(n+r-1, r)

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

Submission status: Time Limit Exceeded

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

facs = [1] * (n+k)
invs = [1] * (n+k)
nfac = 1
for i in range(1, n+k):
    nfac = nfac * i % mod
    facs[i] = nfac
    invs[i] = pow(facs[i], mod-2, mod)

ans = 0
for i in range(k+1):
    left = facs[i+n-1] * invs[i] * invs[n-1] % mod
    left = left * pow(25, i, mod) % mod
    ans += left * pow(26, k-i, mod) % mod
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

#output
# (o以外) o (o以外) o (f以外) f (何でも)


#こちらもmodで割った余り。maxが決まっていて、大きくない時はこちらが早い。
mod = pow(10, 9) + 7

def cmb(n, r):
    res = 1
    fac = 1
    for i in range(r):
        res *= (n-i)
        res %= mod
        fac *= (i+1)
        fac %= mod
    return res*pow(fac, mod-2, mod) % mod

#重複組み合わせはH(n, r) = cmb(n+r-1, r)

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

Submission status: Time Limit Exceeded

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

U = n+k
fact = [0]*(U+1)
fact[0] = 1
for i in range(1, U+1):
    fact[i] = fact[i-1]*i % MOD


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


def nCr(n, r):
    if r < 0 or n < r:
        return 0
    return fact[n]*invfact[r]*invfact[n-r]


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

Submission status: Time Limit Exceeded

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


def com(n, r):
    X = Y = 1
    if r < 0 or n < r:
        return 0
    if n-r < r:
        r = n-r
    for i in range(1, r+1):
        Y = Y*i % MOD
        X = X*(n-i+1) % MOD
    Y = pow(Y, MOD-2, MOD)
    return X*Y % MOD


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

Submission status: Time Limit Exceeded

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


def com(n, r):
    X = Y = 1
    if r < 0 or n < r:
        return 0
    if n-r < r:
        r = n-r
    for i in range(1, r+1):
        Y = Y*i % MOD
        X = X*(n-i+1) % MOD
    Y = pow(Y, MOD-2, MOD)
    return X*Y % MOD


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

Submission status: Time Limit Exceeded

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


def com(n, r):
    X = Y = 1
    if r < 0 or n < r:
        return 0
    if n-r < r:
        r = n-r
    for i in range(1, r+1):
        Y = Y*i % MOD
        X = X*(n-i+1) % MOD
    Y = pow(Y, MOD-2, MOD)
    return X*Y % MOD


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

Submission status: Time Limit Exceeded

Solution code:
k, s = open(0).read().split()
k = int(k)
n = len(s)
mod = 10**9+7
ans = 0

def c(a, b):
    n = 1
    d = 1
    for i in range(b):
        n *= (a - i)
        d *= (b - i)
    return n // d

for i in range(k+1):
    tmp = pow(26, k-i, mod)
    tmp *= pow(25, i, mod)
    tmp *= c(i+n-1, n-1)
    ans += tmp

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    K = int(input())
    S = input()
    N = len(S)

    MOD = 10**9+7
    n = N+K
    fac = [1]*(n+1)
    rev = [1]*(n+1)
    
    for i in range(1,n+1):
        fac[i] = i*fac[i-1]%MOD
        rev[i] = pow(fac[i], MOD-2, MOD)
    
    comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD

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


solve()