Problem:


Score: 600 points

Problem Statement

How many strings can be obtained by applying the following operation on a string S exactly K times: "choose one lowercase English letter and insert it somewhere"?

The answer can be enormous, so print it modulo (10^9+7).

Constraints

K is an integer between 1 and 10^6 (inclusive).

S is a string of length between 1 and 10^6 (inclusive) consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

K
S

Output

Print the number of strings satisfying the condition, modulo (10^9+7).

Sample Input 1

5
oof

Sample Output 1

575111451

For example, we can obtain proofend, moonwolf, and onionpuf, while we cannot obtain oofsix, oofelevennn, voxafolt, or fooooooo.

Sample Input 2

37564
whydidyoudesertme

Sample Output 2

318008117



Sample input:
5
oof


Sample output:
575111451

Submission status: Accepted

Solution code:
def COMinit():
    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 COM(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

mod = 10**9+7

K = int(input())
S = input()
N = len(S)
max = N+K
fac = [0] * max
finv = [0] * max
inv = [0] * max
COMinit()

ans = 0
for i in range(K+1):
    x = COM(N+K-i-1,N-1)
    y = pow(26,i,mod)
    z = pow(25,K-i,mod)
    xyz = ((x*y%mod)*z)%mod
    ans = (ans+xyz)%mod
print(ans)

Submission status: Accepted

Solution code:
# 解説参照
k = int(input())
n = len(input())

mod = 10 ** 9 + 7
f = [1] + [1]
for i in range(2, n + k + 1 + 26):
    f.append(f[-1] * i % mod)

inv = [0] + [1]
for i in range(2, n + k + 2 + 26):
    inv += [inv[mod % i] * (mod - int(mod / i)) % mod]

inv_f = [1, 1]
for i in range(2, n + k + 2 + 26):
    inv_f.append(inv_f[-1] * inv[i] % mod)


def c(x, y):
    return f[x] * inv_f[x - y] * inv_f[y]


ans = 0

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

print(ans % mod)

Submission status: Accepted

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

MOD = 10 ** 9 + 7
modinv = lambda a, mod=MOD: pow(a, MOD - 2, mod)

# x: 26^k*25^(K-k)
x = pow(26, K, MOD)

# comb: C(L+K-i-1, L-1)
comb = 1

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

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

"""
dp[i][j]を
「i文字目まででj回Sの文字を使ったか」とする

K = 5
S = 'oof'
dp = [[0] * (len(S) + 1) for i in range(K + len(S) + 1)]
dp[0][0] = 1

for i in range(1, K + len(S) + 1):
    for j in range(len(S) + 1):
        if j < len(S):
            dp[i][j] += dp[i - 1][j] * 25
        else:
            dp[i][j] += dp[i - 1][j] * 26 # j回使い切るともうSは関係なくなるので *= 26になる
        if j >= 1:
            dp[i][j] += dp[i - 1][j - 1]

l_s = len(S)
どのタイミングで「この先ずっと*= 26」になるか
後ろからi文字目にSを使い切る: pow(25, K - k, mod) * cmb(N + K - k - 1, N - 1) * pow(26, k, mod)
...
"""

lim = 2 * (10 ** 6) + 1
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, lim + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    # 累計
    factinv.append((factinv[-1] * inv[-1]) % mod)

def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    if r == 0:
        return 1
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % mod

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

ans = 0
# l_s + i文字目に文字を使い切る
# 次から *= 26
for k in range(K + 1):
    # 逆からやってる
    ans += cmb(N + K - k - 1, N - 1) * pow(26, k, mod) * pow(25, K - k, mod) % mod
    ans %= mod

print(ans)

Submission status: Accepted

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


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):
        if n < r or n < 0 or r < 0:
            return 0
        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(2100000)
ans = 0
for i in range(K + 1):

    temp = comb(N + K - i - 1, N - 1)
    temp %= MOD
    temp *= pow(26, i, MOD)
    temp %= MOD
    temp *= pow(25, K - i, MOD)
    temp %= MOD
    ans += temp
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
MAX = 5*10**6 + 1

fact = [0 for _ in range(MAX)]
factinv = [0 for _ in range(MAX)]

fact[0] = 1
for k in range(1, MAX):
    fact[k] = fact[k - 1]*k
    fact[k] %= MOD

factinv[MAX - 1] = pow(fact[MAX - 1], MOD - 2, MOD)
for k in range(MAX - 1, 0, -1):
    factinv[k - 1] = factinv[k]*k
    factinv[k - 1] %= MOD

def nCk(n, k):
    return fact[n]*factinv[k]*factinv[n - k] % MOD

def nPk(n, k):
    return fact[n]*factinv[n - k] % MOD

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

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

print(ans)

Submission status: Accepted

Solution code:
#解説参照
k=int(input())
n=len(input())

mod=10**9+7
f=[1]+[1]
for i in range(2,n+k+1+26):
    f.append(f[-1]*i%mod)


inv = [0]+[1]
for i in range(2,n+k+2+26):
  inv += [inv[mod % i] * (mod - int(mod / i)) % mod]
 
inv_f=[1,1]
for i in range(2,n+k+2+26):
    inv_f.append(inv_f[-1]*inv[i]%mod)

def c(x,y):
    return f[x]*inv_f[x-y]*inv_f[y]
ans=0
prod=pow(25,k,mod)
for i in range(k+1):
    ans+=c(n+k-i-1,n-1)*prod#pow(25,k-i,mod)*pow(26,i,mod)
    prod*=26
    prod*=inv[25]
    prod%=mod
print(ans%mod)

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
nmax = 2*10**6+2
mod = 10**9+7
fac = [1]*nmax
finv = [1]*nmax
inv = [1]*nmax
def ncr_pre():
    for i in range(2,nmax):
        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 ncr(n,r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fac[n]* (finv[r] * finv[n-r] %mod) %mod

ncr_pre()
k = ni()
s = input()
n = len(s)
ans= 0
for i in range(k+1):
    ans=(ans+ ncr(n+k-i-1,n-1)*pow(25,k-i,mod)*pow(26,i,mod) )%mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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

fac = [1] * (K + l + 1)
for i in range(1, K + l + 1):
	fac[i] = (fac[i - 1] * i) % MOD

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

ans = 0
for en in range(l - 1, l + K):
	t = (fac[en] * pow(fac[en - l + 1], MOD - 2, MOD) * pow(fac[l - 1], MOD - 2, MOD)) % MOD
	t = (t * p25[en - l + 1]) % MOD
	t = (t * p26[l + K - 1 - en]) % MOD
	ans = (ans + t) % MOD
print(ans)

Submission status: Accepted

Solution code:
class Combination:
    """
    SIZEが10^6程度以下の二項係数を何回も呼び出したいときに使う
    使い方:
    comb = Combination(SIZE, MOD)
    comb(10, 3) => 120
    """

    def __init__(self, N, MOD=10 ** 9 + 7):
        self.MOD = MOD
        self.fact, self.inv = self._make_factorial_list(N)

    def __call__(self, n, k):
        if k < 0 or k > n:
            return 0
        res = self.fact[n] * self.inv[k] % self.MOD
        res = res * self.inv[n - k] % self.MOD
        return res

    def _make_factorial_list(self, N):
        fact = [1] * (N + 1)
        inv = [1] * (N + 1)
        MOD = self.MOD
        for i in range(1, N + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            inv[i - 1] = (inv[i] * i) % MOD
        return fact, inv


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

mod = 10 ** 9 + 7
comb = Combination(3 * 10 ** 6, mod)

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

print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 10**9 + 7
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    K = NI()
    S = SI()
    LS = len(S)

    f = [0] * (K+LS)
    r = [0] * (K+LS)
    f[0] = 1
    r[0] = 1
    c = 1
    for i in range(1, K + LS):
        c = (c * i) % MOD
        f[i] = c
        r[i] = pow(c, MOD - 2, MOD)

    def comb(n, k):
        return (f[n] * r[k] * r[n - k]) % MOD

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 10**9 + 7
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    K = NI()
    S = SI()
    LS = len(S)

    f = [1] * (K+LS)
    r = [1] * (K+LS)
    c = 1
    for i in range(1, K + LS):
        c = (c * i) % MOD
        f[i] = c
        r[i] = pow(c, MOD - 2, MOD)

    def comb(n, k):
        return (f[n] * r[k] * r[n - k]) % MOD

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = float('inf')
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    K = NI()
    S = SI()
    LS = len(S)

    f = [1]
    r = [1]
    c = 1
    for i in range(1, K + LS +1):
        c = (c * i) % MOD
        f.append(c)
        r.append(pow(c, MOD - 2, MOD))

    def comb(n, k):
        return (f[n] * r[k] * r[n - k]) % MOD

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = float('inf')
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    K = NI()
    S = SI()

    f = [1]
    r = [1]
    c = 1
    for i in range(1, K + len(S)+1):
        c = (c * i) % MOD
        f.append(c)
        r.append(pow(c, MOD - 2, MOD))

    def comb(n, k):
        return (f[n] * r[k] * r[n - k]) % MOD

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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


mod = 10**9 + 7

b = mod-2
blis = []
c = 0
while b >0:
  if b & 1 == 1:
    blis.append(c)
  c += 1
  b >>= 1

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(c):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res *li[item] %mod
    return res

from collections import deque

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, K + S + 1):
  fact.append((fact[-1] * i) % mod)
  if i < K+2:
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

factinv_k = deque(factinv[:K+1])
fact_ks = deque(fact[S-1:])


list26 = deque([1])
list25 = deque([1])
now26 = 26
now25 = 25
for k in range(K):
  list25.append(now25)
  list26.append(now26)
  now25 = now25*25%mod
  now26 = now26*26%mod


ans = 0
for k in range(K+1):
  now = list26.pop()
  now = now * list25.popleft() % mod
  now = now * fact_ks.popleft() % mod
  now = now * factinv_k.popleft() %mod
  ans += now
  ans %= mod


ans *= modinv(fact[S-1])
ans %= mod
print(ans)

Submission status: Accepted

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: Accepted

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 = 2*(10**6)
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()
L = len(S)

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

print(ans)

Submission status: Accepted

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

MOD = 10**9+7
def frac(limit):
    frac = [1]*limit
    for i in range(2,limit):
        frac[i] = i * frac[i-1]%MOD
    fraci = [None]*limit
    fraci[-1] = pow(frac[-1], MOD -2, MOD)
    for i in range(-2, -limit-1, -1):
        fraci[i] = fraci[i+1] * (limit + i + 1) % MOD
    return frac, fraci
frac, fraci = frac(2341398)
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*fraci[b]*fraci[a-b]%MOD

K = int(readline())
S = len(readline().strip())
ans = 0

M = 1341398
A = [1]*M
B = [1]*M
for i in range(1, M):
    A[i] = (A[i-1]*25)%MOD
    B[i] = (B[i-1]*26)%MOD

ans = 0

for i in range(K+1):
    ans = (ans+A[i]*B[K-i]*comb(i+S-1, i))%MOD

print(ans)

Submission status: Accepted

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

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20

class Counting():
    def __init__(self,maxim,mod):
        maxim += 1

        self.mod = mod
        self.fact = [0]*maxim
        self.fact[0] = 1
        for i in range(1,maxim):
            self.fact[i] = self.fact[i-1] * i % mod

        self.invfact = [0]*maxim
        self.invfact[maxim-1] = pow(self.fact[maxim-1],mod-2,mod)
        for i in reversed(range(maxim-1)):
            self.invfact[i] = self.invfact[i+1] * (i+1) % mod


    def nCk(self,n,r):
        if n < 0 or n < r: return 0
        return self.fact[n] * self.invfact[r] * self.invfact[n-r] % self.mod

    def nPk(self,n,r):
        if n < 0 or n < r: return 0
        return self.fact[n] * self.invfact[n-r] % self.mod




def main():
    K=ii()
    S=list(input())
    N=len(S)
    MOD = 10**9+7

    comb = Counting(N+K+10,MOD)
    ans = 0
    for x in range(K+1):
        ans += comb.nCk(N+K-(x+1),N-1) * pow(25,K-x,MOD) * pow(26,x,MOD) % MOD
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

n=len(s)

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

def p(n,r,mod):
    return fact[n]*factinv[n-r] % mod
mod = 10 ** 9 + 7
maxi = 2*10 ** 6 + 1  # 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, maxi + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

array_5=[1]
array_6=[1]
for i in range(k):
    array_5.append(25*array_5[-1]%mod)
    array_6.append(26*array_6[-1]%mod)

ans=0
for i in range(n,n+k+1): #iはS_Nの固定した位置を表す。
    x=cmb(i-1,n-1,mod)
    y=array_5[i-n]*array_6[n+k-i]
    ans += x*y%mod
    ans %=mod
print(ans)

Submission status: Accepted

Solution code:
def cmb(n, r):
    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+10
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())
n=len(input())
ans=0
for i in range(k,-1,-1):
  ans=(ans+cmb(k+n,i)*pow(25,i,mod))%mod
print(ans)

Submission status: Accepted

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

s = len(S)
mod = int(1e9+7)


n = pow(26, K, mod)
ans = n

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


print(ans)

Submission status: Accepted

Solution code:
K=int(input())
L=len(input())
from numba import*
@njit(cache=1)
def f():
    m=10**9+7
    max_n=2*10**6
    fac=[1]*(max_n+1)
    inv=[1]*(max_n+1)
    ifac=[1]*(max_n+1)
    for n in range(2,max_n+1):
        fac[n]=(fac[n-1]*n)%m
        inv[n]=m-inv[m%n]*(m//n)%m
        ifac[n]=(ifac[n-1]*inv[n])%m
    d=[1]*(K+1)
    d2=[1]*(K+1)
    for i in range(K):
        d[i+1]=d[i]*25%m
        d2[i+1]=d2[i]*26%m
    a=0
    for i in range(K+1):
        a=(a+fac[L+i-1]*ifac[i]%m*ifac[L-1]%m*d[i]%m*d2[K-i]%m)%m
    return a
print(f())

Submission status: Accepted

Solution code:
def pows(a, n, mod):
    # [a**0, a**1, ..., a**n] % mod
    ret = [1] * (n + 1)
    for i in range(1, n + 1):
        ret[i] = ret[i - 1] * a % mod
    return ret


def ext_euc(a, b):
    if b == 0:
        return 1, 0, a
    y, x, v = ext_euc(b, a % b)
    y -= (a // b) * x
    return x, y, v


def mod_inv(a, mod):
    x, _, _ = ext_euc(a, mod)
    return x % mod


def main():
    MOD = 10**9 + 7
    K = int(input())
    S = input()
    N = len(S)
    ans = 0
    pw25 = pows(25, K, MOD)
    pw26 = pows(26, K, MOD)
    comb = 1  # (k+N-1)_C_k
    for k in range(K + 1):
        ans += pw25[k] * comb * pw26[K - k]
        ans %= MOD
        comb *= k + N
        comb *= mod_inv(k + 1, MOD)
        comb %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
K=int(input())
S=input()
N=len(S)
p=10**9+7
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+K ):
    fact.append((fact[-1] * i) % p) # [-1]は後ろから?
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
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
A=0
TF=[1]
TS=[1]
for i in range(K+1):
    TF.append(TF[i]*25 %p)
    TS.append(TS[i]*26 %p)
for i in range(K+1): # Sに含まれる文字を加えるときは、必ず後ろであると考え、S[N-1]の(Sの文字を除いた)位置をiとする
    A=(A+TF[i]*TS[K-i]*cmb(i+N-1,i,p)) %p
print(A)

Submission status: Accepted

Solution code:
K = int(input())
S = input()
 
MAX = 2 * 10 ** 6 + 10
MOD = 10 ** 9 + 7
 
# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1
 
# Inverse
inv = [0] * (MAX + 1)
inv[1] = 1
 
# Inverse factorial
finv = [0] * (MAX + 1)
finv[0] = 1
finv[1] = 1
 
for i in range(2, MAX + 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
 
 
def comb(n, k):
    if n < k or k < 0:
        return 0
    return (fac[n] * finv[k] * finv[n - k]) % MOD
 
 
ans = 0
n = len(S)
for k in range(K + 1):
    tmp = (pow(25, K - k, MOD) * pow(26, k, MOD)) % MOD
    ans += comb(n + K - k - 1, n - 1) * tmp % MOD
    ans %= MOD
 
print(ans)

Submission status: Accepted

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

MAX = 2 * 10 ** 6 + 10
MOD = 10 ** 9 + 7

# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1

# Inverse
inv = [0] * (MAX + 1)
inv[1] = 1

# Inverse factorial
finv = [0] * (MAX + 1)
finv[0] = 1
finv[1] = 1

for i in range(2, MAX + 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


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


ans = 0
n = len(S)
for k in range(K + 1):
    tmp = (pow(25, K - k, MOD) * pow(26, k, MOD)) % MOD
    ans += comb(n + K - k - 1, n - 1) * tmp % MOD
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
def setFact(n, mod):
    global fact
    global ifact
    fact = [0]*(n+1)
    fact[0] = 1
    ifact = [0] * (n+1)
    for i in range(1, n+1):
        fact[i] = (fact[i-1]*i)%mod
    ifact[n] = pow(fact[n], mod-2, mod)
    for i in range(1, n+1):
        ifact[n-i] = ifact[n-i+1]*(n-i+1)%mod
def combination(n, k, mod):
    global fact
    global ifact
    if k < 0 or k > n:
        return 0
    else:
        return fact[n]*ifact[n-k]*ifact[k]%mod
k = int(input())
s = input()
n = len(s)
mod = 10**9 + 7
ans = 0
setFact(n+k, mod)
for i in range(k+1):
    now = 1
    now *= pow(26, i, mod)
    now %= mod
    now *= pow(25, k-i, mod)
    now %= mod
    now *= combination(k-i+n-1,n-1 , mod)
    now %= mod
    ans += now
    ans %= mod
print(ans)

Submission status: Accepted

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

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

DIV = 10 ** 9 + 7
n = (10 ** 6) * 5
g1 = [1] * 2 + [0] * (n - 2) # 元テーブル
g2 = [1] * 2 + [0] * (n - 2) #逆元テーブル
inverse = [0, 1] + [0] * (n - 2) #逆元テーブル計算用テーブル

for i in range(2, n):
  g1[i] = (g1[i - 1] * i ) % DIV
  inverse[i] = (-inverse[DIV % i] * (DIV // i)) % DIV
  g2[i] = (g2[i - 1] * inverse[i]) % DIV

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

# K = 3, S = 5のとき
# ..X.X.X.
# Xが取る3か所を選んだ上で、
# 最も右のXよりも右のマス：各26通り
# 最も右のXを含む、それより左のマス：Xのマスは1通り、それ以外は各25通り
# 最も右のXが
# ..X.....　の状態から、
# .......X  
# の状態について、場合の数を求める

ans = 0
for xpos in range(S, N + 1):
  # xpos箇所からK箇所を選ぶ場合の数
  # 一番右に1個固定した状態で、残りのxpos - 1か所からS - 1個を選ぶ
  pat = nCr(xpos - 1, S - 1, DIV)
  # その場合の数に対して、X以外の文字の選び方は25 ** (X - S)通りある
  pat *= pow(25, xpos - S, DIV)
  pat %= DIV
  
  # 残りのマスに対しては26通りずつ選べる
  pat *= pow(26, N - xpos, DIV)
  pat %= DIV
  
  ans += pat
  ans %= DIV

print(ans)

Submission status: Accepted

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

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

DIV = 10 ** 9 + 7
n = (10 ** 6) * 2
g1 = [1] * 2 + [0] * (n - 2) # 元テーブル
g2 = [1] * 2 + [0] * (n - 2) #逆元テーブル
inverse = [0, 1] + [0] * (n - 2) #逆元テーブル計算用テーブル

for i in range(2, n):
  g1[i] = (g1[i - 1] * i ) % DIV
  inverse[i] = (-inverse[DIV % i] * (DIV // i)) % DIV
  g2[i] = (g2[i - 1] * inverse[i]) % DIV

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

# K = 3, S = 5のとき
# ..X.X.X.
# Xが取る3か所を選んだ上で、
# 最も右のXよりも右のマス：各26通り
# 最も右のXを含む、それより左のマス：Xのマスは1通り、それ以外は各25通り
# 最も右のXが
# ..X.....　の状態から、
# .......X  
# の状態について、場合の数を求める

ans = 0
for xpos in range(S, N + 1):
  # xpos箇所からK箇所を選ぶ場合の数
  # 一番右に1個固定した状態で、残りのxpos - 1か所からS - 1個を選ぶ
  pat = nCr(xpos - 1, S - 1, DIV)
  # その場合の数に対して、X以外の文字の選び方は25 ** (X - S)通りある
  pat *= pow(25, xpos - S, DIV)
  pat %= DIV
  
  # 残りのマスに対しては26通りずつ選べる
  pat *= pow(26, N - xpos, DIV)
  pat %= DIV
  
  ans += pat
  ans %= DIV

print(ans)

Submission status: Accepted

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

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

DIV = 10 ** 9 + 7
n = (10 ** 6) * 5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

# K = 3, S = 5のとき
# ..X.X.X.
# Xが取る3か所を選んだ上で、
# 最も右のXよりも右のマス：各26通り
# 最も右のXを含む、それより左のマス：Xのマスは1通り、それ以外は各25通り
# 最も右のXが
# ..X.....　の状態から、
# .......X  
# の状態について、場合の数を求める

ans = 0
for xpos in range(S, N + 1):
  # xpos箇所からK箇所を選ぶ場合の数
  # 一番右に1個固定した状態で、残りのxpos - 1か所からS - 1個を選ぶ
  pat = nCr(xpos - 1, S - 1, DIV)
#  print("xpos",xpos,"ncr",ncr)
#  print(S,"from",xpos,"pat",pat)
  # その場合の数に対して、X以外の文字の選び方は25 ** (X - S)通りある
#  print("25 for",xpos - S,"boxes")
  pat *= pow(25, xpos - S, DIV)
  pat %= DIV
  
  # 残りのマスに対しては26通りずつ選べる
#  print("26 for ",N - xpos,"boxes")
  pat *= pow(26, N - xpos, DIV)
  pat %= DIV
#  print("xpos",xpos,"pat",pat)
  
  ans += pat
  ans %= DIV

print(ans)

Submission status: Accepted

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

MOD = 10 ** 9 + 7

ans = 0

fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]


def cmb(n, k, p):
    global fact, factinv
    if (k < 0) or (n < k):
        return 0
    r = min(k, n - k)
    return fact[n] * factinv[k] * factinv[n - k] % p


N = 2 * 10 ** 6
for i in range(2, N + 10):
    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(K + 1):
    ans += pow(25, i, MOD) * cmb(i + len(S) - 1, len(S) - 1, MOD) * pow(26, K - i, MOD)
    ans %= MOD

print(ans)

Submission status: Accepted

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

MAXN = K+L+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

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

def COMinit(n,MOD):
    fac,finv,inv=[0]*max(2,n+1),[0]*max(2,n+1),[0]*max(2,n+1)
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    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
    return fac,finv,inv

fac,finv,inv=COMinit(K+S,MOD)

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


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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
K = int(input())
S = list(input())[: -1]
N = len(S)
mod = 10 ** 9 + 7

class Factorial:
  def __init__(self, n, mod):
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod

f = Factorial(N + K + 1, mod)

res = 0
for l in range(K + 1):
  r = K - l
  res += f.combi(l + N - 1, l) * pow(25, l, mod) % mod * pow(26, r, mod) % mod
  res %= mod
print(res)

Submission status: Accepted

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

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

g1=[1,1]
g2=[1,1]
inv=[0,1]
for i in range(2,3000003):
  g1.append((g1[-1]*i)%mod)
  inv.append((-inv[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inv[-1])%mod)
P=0
for i in range(K+1):
  P+=pow(26,i,mod)*pow(25,K-i,mod)*cmb(N+K-i-1,K-i)
print(P%mod)