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: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
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(2*10**6,mod)
for i in range(M):
    ans-=c.combi(N,i)*pow(25,N-i,mod)
    ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from scipy.special import comb
input = sys.stdin.readline

K = int(input())
S = input()
s = len(S)
mod = 10**9+7

ans = int(pow(25, K, mod)*(comb(K+s-1, s-1) % mod)) % mod
pre = ans

for i in range(1, K+1):
    new = int(pre*(K-i+1)/(K+s-i)*(26/25)) % mod
    ans = (ans + new) % mod
    pre = new
print(ans)

Submission status: Runtime Error

Solution code:
K = int(input())
S = input()
M = K + len(S)
alpha = "abcdefghijklmnopqrstuvwxyz"
mod = int(1e9) + 7 # <-- input modulo
maxf = 200000           # <-- input factional limitation

def doubling(n, m, modulo=mod):
    y = 1
    base = n
    tmp = m
    while tmp != 0:
        if tmp % 2 == 1:
            y *= base
            if modulo > 0:
                y %= modulo
        base *= base
        if modulo > 0:
            base %= modulo
        tmp //= 2
    return y

def inved(a, modulo=mod):
    x, y, u, v, k, l = 1, 0, 0, 1, a, modulo
    while l != 0:
        x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
        k, l = l, k % l
    return x % modulo

fact = [1 for _ in range(maxf+1)]
invf = [1 for _ in range(maxf+1)]

for i in range(maxf):
    fact[i+1] = (fact[i] * (i+1)) % mod
invf[-1] = inved(fact[-1])
for i in range(maxf, 0, -1):
    invf[i-1] = (invf[i] * i) % mod
  
SS = 0
bas = 1
for i in range(M, len(S)-1, -1):
  SS += (bas * invf[i] * invf[M-i]) % mod
  bas *= 25
  bas %= mod
  SS %= mod
print(SS*fact[M]%mod)

Submission status: Runtime Error

Solution code:
import sys
from scipy.special import comb
input = sys.stdin.readline

K = int(input())
S = input()
s = len(S)
mod = 10**9+7
k25 = pow(25, K, mod)

ans = int(k25*comb(K+s-1, s-1)) % mod
pre = ans

for i in range(1, K+1):
    new = int(pre*(K-i+1)/(K+s-i)*(26/25)) % mod
    ans = (ans + new) % mod
    pre = new
print(ans)

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7


def solveBrute(K, S):
    # On the i-th iteration, dp[j] counts all strings of length i which contains S[:j] as a subsequence

    N = len(S)
    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(N + K):
        nextDp = [0] * (N + 1)
        for j in range(N):
            nextDp[j] += dp[j] * 25
            nextDp[j + 1] += dp[j]
        nextDp[N] += dp[N] * 26

        dp = nextDp
        for j in range(N + 1):
            dp[j] %= MOD
        # print(dp)

    return dp[N]


def solveBrute2(K, S):
    import numpy as np

    def matrixPower(mat, k):
        assert k >= 0
        if k == 0:
            return np.eye(mat.shape[0], dtype=np.int64)
        if k == 1:
            return mat
        temp = matrixPower(mat, k // 2)
        ret = (temp @ temp) % MOD
        if k % 2:
            return (ret @ mat) % MOD
        return ret

    # For intution, can interpret the bruteforce as a matrix multiplication:
    # {{0, 0, 0, 1}} . MatrixPower[{{25, 0, 0, 0}, {1, 25, 0, 0}, {0, 1, 25, 0}, {0, 0, 1, 26}}, 8] . {{1}, {0}, {0}, {0}}
    # https://www.wolframalpha.com/input/?i=%7B%7B0%2C+0%2C+0%2C+1%7D%7D+.+MatrixPower%5B%7B%7B25%2C+0%2C+0%2C+0%7D%2C+%7B1%2C+25%2C+0%2C+0%7D%2C+%7B0%2C+1%2C+25%2C+0%7D%2C+%7B0%2C+0%2C+1%2C+26%7D%7D%2C+8%5D+.+%7B%7B1%7D%2C+%7B0%7D%2C+%7B0%7D%2C+%7B0%7D%7D

    N = len(S)

    mat = 25 * np.eye(N + 1, dtype=np.int64,)
    mat[N][N] += 1
    for i in range(N):
        mat[i + 1][i] = 1

    vec = np.zeros((N + 1, 1), dtype=np.int64)
    vec[0] = 1

    res = matrixPower(mat, N + K) @ vec
    return int(res[N]) % MOD


def solve(K, S):
    def modInverse(a, p):
        # Fermat's little theorem, a**(p-1) = 1 mod p
        return pow(a, p - 2, p)

    # Precompute all factorials
    fact = [1]
    for i in range(1, (10 ** 6) + 1):
        fact.append((fact[-1] * i) % MOD)

    def nCr(n, r, p=MOD):
        # Modulo binomial coefficients
        return (fact[n] * modInverse(fact[r], p) * modInverse(fact[n - r], p)) % p

    total = 0
    N = len(S)
    for i in range(N, N + K + 1):
        total += nCr(N + K, N + K - i) * pow(25, N + K - i, MOD)
        total %= MOD
    return total


(K,) = [int(x) for x in input().split()]
S = input()
ans = solve(K, S)
# assert ans == solveBrute(K, S) == solveBrute2(K, S)
print(ans)

Submission status: Runtime Error

Solution code:
from functools import reduce
def comb(n, A):
    bunsi = reduce(lambda x, y: x*y%mod, range(n, n-A, -1))
    bunbo = reduce(lambda x, y: x*y%mod, range(1, A+1))
    return bunsi * pow(bunbo, mod-2, mod) % mod

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

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7


def solveBrute(K, S):
    # On the i-th iteration, dp[j] counts all strings of length i which contains S[:j] as a subsequence

    N = len(S)
    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(N + K):
        nextDp = [0] * (N + 1)
        for j in range(N):
            nextDp[j] += dp[j] * 25
            nextDp[j + 1] += dp[j]
        nextDp[N] += dp[N] * 26

        dp = nextDp
        for j in range(N + 1):
            dp[j] %= MOD
        # print(dp)

    return dp[N]


def solveBrute2(K, S):
    import numpy as np

    def matrixPower(mat, k):
        assert k >= 0
        if k == 0:
            return np.eye(mat.shape[0], dtype=np.int64)
        if k == 1:
            return mat
        temp = matrixPower(mat, k // 2)
        ret = (temp @ temp) % MOD
        if k % 2:
            return (ret @ mat) % MOD
        return ret

    # For intution, can interpret the bruteforce as a matrix multiplication:
    # {{0, 0, 0, 1}} . MatrixPower[{{25, 0, 0, 0}, {1, 25, 0, 0}, {0, 1, 25, 0}, {0, 0, 1, 26}}, 8] . {{1}, {0}, {0}, {0}}
    # https://www.wolframalpha.com/input/?i=%7B%7B0%2C+0%2C+0%2C+1%7D%7D+.+MatrixPower%5B%7B%7B25%2C+0%2C+0%2C+0%7D%2C+%7B1%2C+25%2C+0%2C+0%7D%2C+%7B0%2C+1%2C+25%2C+0%7D%2C+%7B0%2C+0%2C+1%2C+26%7D%7D%2C+8%5D+.+%7B%7B1%7D%2C+%7B0%7D%2C+%7B0%7D%2C+%7B0%7D%7D

    N = len(S)

    mat = 25 * np.eye(N + 1, dtype=np.int64,)
    mat[N][N] += 1
    for i in range(N):
        mat[i + 1][i] = 1

    vec = np.zeros((N + 1, 1), dtype=np.int64)
    vec[0] = 1

    res = matrixPower(mat, N + K) @ vec
    return int(res[N]) % MOD


def solve(K, S):
    def modInverse(a, p):
        # Fermat's little theorem, a**(p-1) = 1 mod p
        return pow(a, p - 2, p)

    # Precompute all factorials
    fact = [1]
    for i in range(1, (10 ** 6) + 1):
        fact.append((fact[-1] * i) % MOD)

    def nCr(n, r, p=MOD):
        # Modulo binomial coefficients
        return (fact[n] * modInverse(fact[r], p) * modInverse(fact[n - r], p)) % p

    total = 0
    N = len(S)
    for i in range(N, N + K + 1):
        total += nCr(N + K, i) * pow(25, N + K - i, MOD)
        total %= MOD
    return total


(K,) = [int(x) for x in input().split()]
S = input()
ans = solve(K, S)
# assert ans == solveBrute(K, S) == solveBrute2(K, S)
print(ans)

Submission status: Runtime Error

Solution code:
from scipy.special import comb
from collections import defaultdict 
k = int(input())
s = input()

len_s = len(s)
max_len = k+len_s

mod = 10**9 + 7

power_dict = defaultdict(lambda:1)
def mod_pow(n,power,mod):
    ans = 1
    if power_dict[(n,power)] != 1:
        return power_dict[(n,power)]
        
    i = power
    while power_dict[(n,i)] == 1 and i > 0:
        i -= 1
    ans = power_dict[(n,i)]

    for x in range(i,power):
        ans = ans * n % mod
        power_dict[(n,x+1)] = ans
    return ans

ans = 0
for i in range(len_s,max_len+1):
    #i = sn
    after = mod_pow(26,max_len-i, mod)
    before = mod_pow(25,i - len_s,mod)
    sn_change = i-1
    sn = int(comb(sn_change,len_s-1)) % mod
    ans += (after * before * sn)
    ans = ans % mod
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
readline = sys.stdin.buffer.readline

MOD = 10 ** 9 + 7


def main(K, N, MOD):
    def cumprod(A, mod=MOD):
        L = len(A)
        Lsq = int(L**.5 + 1)
        A = np.resize(A, Lsq**2).reshape(Lsq, Lsq)
        for n in range(1, Lsq):
            A[:, n] *= A[:, n - 1]
            A[:, n] %= mod
        for n in range(1, Lsq):
            A[n] *= A[n - 1, -1]
            A[n] %= mod
        return A.ravel()[:L]

    def make_fact(U, mod=MOD):
        x = np.arange(U, dtype=np.int64)
        x[0] = 1
        fact = cumprod(x, mod)
        x = np.arange(U, 0, -1, dtype=np.int64)
        x[0] = pow(int(fact[-1]), mod - 2, mod)
        fact_inv = cumprod(x, mod)[::-1]
        fact.flags.writeable = False
        fact_inv.flags.writeable = False
        return fact, fact_inv

    fac, finv = make_fact(2_000_010, MOD)
    f = np.zeros(K + 1, np.int64)
    f = fac[N - 1:K + N] * finv[N - 1] % MOD * finv[:K + 1] % MOD

    x = 1
    for i in range(1, K + 1):
        x = (x * 25) % MOD
        f[i] = f[i] * x % MOD
    for i in range(1, K + 1):
        f[i] += f[i - 1] * 26
        f[i] %= MOD
    return f[-1]


if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.from_dtype(np.int64)
    signature = (i8, i8, i8)
    cc = CC('my_module')
    cc.export('main', signature)(main)
    cc.compile()

from my_module import main
K = int(readline())
N = len(readline())
print(main(K, N, MOD))

Submission status: Runtime Error

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

mod=10**9+7

import sys
sys.setrecursionlimit(10**9)

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
p = mod #割る数
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

ans=0

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

    #print(end,len(s)+k-end,ans,cmb(end,len(s),mod),pow(25,end-len(s),mod),pow(26,len(s)+k-end,mod))

print(ans%mod)

Submission status: Runtime Error

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

mod=10**9+7

import sys
sys.setrecursionlimit(10**15)

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
p = mod #割る数
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

ans=0

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

    #print(end,len(s)+k-end,ans,cmb(end,len(s),mod),pow(25,end-len(s),mod),pow(26,len(s)+k-end,mod))

print(ans%mod)

Submission status: Runtime Error

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

mod=10**9+7

import sys
sys.setrecursionlimit(2147483647)

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
p = mod #割る数
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

ans=0

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

    #print(end,len(s)+k-end,ans,cmb(end,len(s),mod),pow(25,end-len(s),mod),pow(26,len(s)+k-end,mod))

print(ans%mod)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')
class BinomialCoefficient(object):

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

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

K = I()
S = input()

bi = BinomialCoefficient(N=10 ** 6 + 1)
ans = 0
# i := Snのindex
for i in range(len(S) - 1, len(S) + K):
    tail = len(S) + K - i - 1
    lans = bi.comb(i, len(S) - 1)
    lans = lans * pow(25, K - tail, MOD) % MOD
    lans = lans * pow(26, tail, MOD) % MOD
    ans = (ans + lans) % MOD
print(ans)

Submission status: Runtime Error

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

mod=10**9+7

import sys
sys.setrecursionlimit(2147483647)

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
p = mod #割る数
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

ans=0

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

    #print(end,len(s)+k-end,ans,cmb(end,len(s),mod),pow(25,end-len(s),mod),pow(26,len(s)+k-end,mod))

print(ans%mod)

Submission status: Runtime Error

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

mod=10**9+7

import sys
sys.setrecursionlimit(2147483647)

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
p = mod #割る数
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

ans=0

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

    #print(end,len(s)+k-end,ans,cmb(end,len(s),mod),pow(25,end-len(s),mod),pow(26,len(s)+k-end,mod))

print(ans%mod)

Submission status: Runtime Error

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

mod=10**9+7

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
p = mod #割る数
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

ans=0

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

    #print(end,len(s)+k-end,ans,cmb(end,len(s),mod),pow(25,end-len(s),mod),pow(26,len(s)+k-end,mod))

print(ans%mod)

Submission status: Runtime Error

Solution code:
from functools import reduce
def comb(n, A):
    bunsi = reduce(lambda x, y: x*y%mod, range(n, n-A, -1))
    bunbo = reduce(lambda x, y: x*y%mod, range(1, A+1))
    return bunsi * pow(bunbo, mod-2, mod) % mod

K = int(input())
s = input()
mod = 10**9 + 7
ans = 0
num = K + len(s)
for i in range(K+1):
    a = 26**i%mod
    a = a*comb(num - i - 1, len(s) - 1)%mod
    a = 25**(K - i)%mod
    ans += a%mod
print(ans%mod)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

comb = Combination(10**6)

def main():
    K = int(input())
    S = deque(input())
    L = len(S)
    """
    dpではなく単純に組み合わせ論だった。。。
    """
    ans = 0
    for x in range(K + 1):
        ans += comb(K - x + L - 1, L - 1) * pow(25, K - x, mod) * pow(26, x, mod)
        ans %= mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from functools import reduce
def comb(n, A):
    bunsi = reduce(lambda x, y: x*y%mod, range(n, n-A, -1))
    bunbo = reduce(lambda x, y: x*y%mod, range(1, A+1))
    return bunsi * pow(bunbo, mod-2, mod) % mod

K = int(input())
s = input()
mod = 10**9 + 7
ans = 0
num = K + len(s)
for i in range(K+1):
    ans += (26**i * comb(num - i - 1, len(s) - 1) * 25**(K - i))%mod
print(ans%mod)

Submission status: Runtime Error

Solution code:
from numba import njit

@njit
def fact_table(N, MOD):
    inv = np.empty(N, np.int64)
    inv[0] = 0
    inv[1] = 1
    for n in range(2, N):
        q, r = divmod(MOD, n)
        inv[n] = inv[r] * (-q) % MOD
    fact = np.empty(N, np.int64)
    fact[0] = 1
    for n in range(1, N):
        fact[n] = n * fact[n - 1] % MOD
    fact_inv = np.empty(N, np.int64)
    fact_inv[0] = 1
    for n in range(1, N):
        fact_inv[n] = fact_inv[n - 1] * inv[n] % MOD
    return fact, fact_inv, inv
mod = 10 **9 +7
k = int(input())
s = input()
len_total = len(s)+k
total = 0

fact, fact_inv, inv = fact_table(len_total, mod)

tmp = fact[len_total-1] * fact_inv[len(s) - 1] %mod
tmp = tmp * fact_inv[len_total - len(s)]%mod
for i in range(k):
    tmp= (tmp*25)%mod
i = len_total
while i >= len(s):
    total = total + tmp
    tmp = (tmp * 26 * (i - len(s)) * pow(25*(i-1), mod-2, mod))%mod
    i -= 1
print(total%mod)

Submission status: Runtime Error

Solution code:
import numpy as np
def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U,MOD):
    x = np.arange(U,dtype=np.int64); x[0] = 1
    fact = cumprod(x,MOD)
    x = np.arange(U,0,-1,dtype=np.int64); x[0] = pow(int(fact[-1]),MOD-2,MOD)
    fact_inv = cumprod(x,MOD)[::-1]
    return fact,fact_inv

U = 10**6
MOD = 10**9+7
fact, invfact = make_fact(U,MOD)

K = int(input())
n = len(input())
ans = 0
for i in range(K+1):
    tmp = pow(26, K-i, MOD)
    tmp = (tmp * pow(25, i, MOD)) % MOD
    tmp = (tmp * (fact[i+n-1] * invfact[i] % MOD * invfact[n-1] % MOD))%MOD  # i+(n-1) C (n-1) = i+(n-1) C i
    ans = (ans + tmp) % MOD
print(ans)

Submission status: Runtime Error

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

pow25 = [1]

ans = 0
for k in range(M, N + 1):
    ans += binom(N, k) * pow25[N - k] % MOD
    ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from functools import lru_cache
sys.setrecursionlimit(1_000_002)

MOD = 1000000007  # type: int

def solve(K: int, S: str):
    '''
    >>> solve(1, 'a')
    51
    '''
    N = len(S)
    mf = ModFactorial(MOD, N+K+1)
    ans = 0    
    for k in range(K+1):
        ans = (ans + mf.combination(k+N-1, k) * pow(25, k, MOD) % MOD * pow(26, K-k, MOD)) % MOD
    return ans

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    print(solve(K, S))

def mod_range(mod, start, stop=None, step=1):    
    if stop == None:
        stop = start
        start = 0
    return map(lambda i: i % mod, range(start, stop, step))

def mod_inv(mod, n):
    '''
    >>> mod_inv(3, 2)
    2
    >>> mod_inv(1000000007, 2)
    500000004
    '''
    return pow(n, mod-2, mod)

def mod_permutation(mod, n, r):
    '''
    >>> mod_permutation(1000000007, 10, 2)
    90
    >>> mod_permutation(7, 10, 2)
    6
    '''
    m = 1
    for i in mod_range(mod, n-r+1, n+1):
        m = (m * i) % mod
    return m

def mod_factorial(mod, n):
    '''
    >>> mod_factorial(1000000007, 10)
    3628800
    >>> mod_factorial(7, 6)
    6
    '''
    return mod_permutation(mod, n, n)

def mod_combination(mod, n, r):
    '''
    >>> mod_combination(1000000007, 10, 2)
    45
    >>> mod_combination(7, 10, 2)
    3
    '''
    return mod_permutation(mod, n, r) * mod_inv(mod, mod_factorial(mod, r)) % mod

class ModFactorial:
    def __init__(self, mod, size=1):
        '''
        >>> ModFactorial(7, 7)
        Traceback (most recent call last):
        ...
        AssertionError
        '''
        assert mod > size
        self._mod = mod
        self._init_factorials(size)

    def _mod_range(self, start, stop=None, step=1):
        return mod_range(self._mod, start, stop, step)
    
    def _mod_inv(self, n):
        return mod_inv(self._mod, n)
    
    def _init_factorials(self, size):
        '''
        >>> mf1 = ModFactorial(1000000007)
        >>> mf2 = ModFactorial(1000000007, 10)
        >>> mf1.factorial(10) == mf2.factorial(10)
        True
        '''
        self._factorials = [1] * size        
        n = 1 # リストの参照は遅いので減らす
        for i, m in enumerate(self._mod_range(1, size), 1):
            n = (n * m) % self._mod
            self._factorials[i] = n
            
    def _append_factorials(self, n):
        for m in map(lambda i: i % self._mod, range(len(self._factorials), n+1)):
            self._factorials.append((self._factorials[-1] * m) % self._mod)

    def factorial(self, n):
        '''
        >>> ModFactorial(1000000007).factorial(10)
        3628800
        >>> ModFactorial(7).factorial(6)
        6
        >>> ModFactorial(7).factorial(7)
        Traceback (most recent call last):
        ...
        AssertionError
        '''
        assert n < self._mod
        if len(self._factorials) <= n:
            self._append_factorials(n)
        return self._factorials[n]

    def factorial_inv(self, n):
        '''
        >>> MOD = 1000000007
        >>> mf = ModFactorial(MOD)
        >>> mf.factorial_inv(10)
        283194722
        >>> mf.factorial_inv(10) * mf.factorial(10) % MOD
        1
        >>> MOD = 7
        >>> mf = ModFactorial(MOD)
        >>> mf.factorial_inv(6)
        6
        >>> mf.factorial_inv(6) * mf.factorial(6) % MOD
        1
        '''
        return self._mod_inv(self.factorial(n))

    def permutation(self, n, r):
        '''
        >>> ModFactorial(1000000007).permutation(10, 2)
        90
        '''
        return self.factorial(n) * self.factorial_inv(n-r) % self._mod

    def combination(self, n, r):
        '''
        >>> ModFactorial(1000000007).combination(10, 2)
        45
        '''
        return self.permutation(n, r) * self.factorial_inv(r) % self._mod

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()
#!/usr/bin/env python3
import sys
from functools import lru_cache
sys.setrecursionlimit(1_000_002)

MOD = 1000000007  # type: int

def solve(K: int, S: str):
    '''
    >>> solve(1, 'a')
    51
    '''
    N = len(S)
    mf = ModFactorial(MOD, N+K+1)
    ans = 0    
    for k in range(K+1):
        ans = (ans + mf.combination(k+N-1, k) * pow(25, k, MOD) % MOD * pow(26, K-k, MOD)) % MOD
    return ans

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    print(solve(K, S))

def mod_range(mod, start, stop=None, step=1):    
    if stop == None:
        stop = start
        start = 0
    return map(lambda i: i % mod, range(start, stop, step))

def mod_inv(mod, n):
    '''
    >>> mod_inv(3, 2)
    2
    >>> mod_inv(1000000007, 2)
    500000004
    '''
    return pow(n, mod-2, mod)

def mod_permutation(mod, n, r):
    '''
    >>> mod_permutation(1000000007, 10, 2)
    90
    >>> mod_permutation(7, 10, 2)
    6
    '''
    m = 1
    for i in mod_range(mod, n-r+1, n+1):
        m = (m * i) % mod
    return m

def mod_factorial(mod, n):
    '''
    >>> mod_factorial(1000000007, 10)
    3628800
    >>> mod_factorial(7, 6)
    6
    '''
    return mod_permutation(mod, n, n)

def mod_combination(mod, n, r):
    '''
    >>> mod_combination(1000000007, 10, 2)
    45
    >>> mod_combination(7, 10, 2)
    3
    '''
    return mod_permutation(mod, n, r) * mod_inv(mod, mod_factorial(mod, r)) % mod

class ModFactorial:
    def __init__(self, mod, size=1):
        '''
        >>> ModFactorial(7, 7)
        Traceback (most recent call last):
        ...
        AssertionError
        '''
        assert mod > size
        self._mod = mod
        self._init_factorials(size)

    def _mod_range(self, start, stop=None, step=1):
        return mod_range(self._mod, start, stop, step)
    
    def _mod_inv(self, n):
        return mod_inv(self._mod, n)
    
    def _init_factorials(self, size):
        '''
        >>> mf1 = ModFactorial(1000000007)
        >>> mf2 = ModFactorial(1000000007, 10)
        >>> mf1.factorial(10) == mf2.factorial(10)
        True
        '''
        self._factorials = [1] * size        
        n = 1 # リストの参照は遅いので減らす
        for i, m in enumerate(self._mod_range(1, size), 1):
            n = (n * m) % self._mod
            self._factorials[i] = n
            
    def _append_factorials(self, n):
        for m in map(lambda i: i % self._mod, range(len(self._factorials), n+1)):
            self._factorials.append((self._factorials[-1] * m) % self._mod)

    def factorial(self, n):
        '''
        >>> ModFactorial(1000000007).factorial(10)
        3628800
        >>> ModFactorial(7).factorial(6)
        6
        >>> ModFactorial(7).factorial(7)
        Traceback (most recent call last):
        ...
        AssertionError
        '''
        assert n < self._mod
        if len(self._factorials) <= n:
            self._append_factorials(n)
        return self._factorials[n]

    def factorial_inv(self, n):
        '''
        >>> MOD = 1000000007
        >>> mf = ModFactorial(MOD)
        >>> mf.factorial_inv(10)
        283194722
        >>> mf.factorial_inv(10) * mf.factorial(10) % MOD
        1
        >>> MOD = 7
        >>> mf = ModFactorial(MOD)
        >>> mf.factorial_inv(6)
        6
        >>> mf.factorial_inv(6) * mf.factorial(6) % MOD
        1
        '''
        return self._mod_inv(self.factorial(n))

    def permutation(self, n, r):
        '''
        >>> ModFactorial(1000000007).permutation(10, 2)
        90
        '''
        return self.factorial(n) * self.factorial_inv(n-r) % self._mod

    def combination(self, n, r):
        '''
        >>> ModFactorial(1000000007).combination(10, 2)
        45
        '''
        return self.permutation(n, r) * self.factorial_inv(r) % self._mod

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Runtime Error

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


@lru_cache
def factorial(n):
    if n == 0:
        return 1
    return (n * factorial(n-1)) % MOD


@lru_cache
def ifactorial(n):
    return pow(factorial(n), MOD-2, MOD)


@lru_cache
def combination(n, k):
    ret = factorial(n) * ifactorial(k)
    ret %= MOD
    ret *= ifactorial(n - k)
    return ret % MOD


k = int(input())
s = input()
MOD = 10**9+7

ans = 0
for i in range(k + 1):
    tmp = combination(i + len(s) - 1, len(s) - 1)
    tmp *= pow(25, i, MOD)
    tmp *= pow(26, k - i, MOD)
    tmp %= MOD
    ans += tmp
    ans %= MOD
print(ans)

Submission status: Runtime Error

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


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


N = 10**6+1
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

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

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