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:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""
mod = 10**9+7 #出力の制限
N = 10**6*2
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
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % mod

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 )
# a = cmb(n,r)

k = onem()

s = input()[:-1]

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

Submission status: Accepted

Solution code:
k = int(input())
s = input()
# k = 10 ** 6
# s = 'a'*10**6
n = len(s)
mod = 10 ** 9 + 7
ans = 0

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 )


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

Submission status: Accepted

Solution code:
def main():

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

    mod = pow(10, 9) + 7
    N = len(S)

    g1 = [1, 1]
    g2 = [1, 1]
    inv = [0, 1]

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

    def combi(n, r):
      r = min(r, n-r)
      return g1[n]*g2[r]*g2[n-r]%mod

    pow25 = [1]
    pow26 = [1]
    for i in range(K):
        pow25.append(pow25[-1] * 25 % mod)
        pow26.append(pow26[-1] * 26 % mod)

    ans = 0
    for i in range(N-1, N+K):
        ans += combi(i, N-1) * pow25[i-N+1] % mod * pow26[K-i+N-1] % mod
        ans %= mod
    return ans

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
class BiCoeff(object):
    def __init__(self, MAX, m):
        super(BiCoeff, self).__init__()
        fac = [0]*MAX
        finv = [0]*MAX
        inv = [0]*MAX

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

        self.MAX = MAX
        self.m = m
        self.fac = fac
        self.finv = finv
        self.inv = inv

    def calc(self,n,k):
        if n<k:
            return 0
        if n<0 or k<0:
            return 0
        return (self.fac[n] * (self.finv[k]*self.finv[n-k])%self.m)%self.m

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

b = BiCoeff(n+k+10, mod)
res = 0
for t in range(k+1):
    res += b.calc(n+k - (t+1), k-t)*pow(25,k-t,mod)*pow(26,t,mod)
    res %= mod
print(res)

Submission status: Accepted

Solution code:
import copy

def com(n,r,m):
    #a = math.factorial(n)%m
    a = 1
    for i in range(1,n+1):
        a *= i
        a %= m
    A = pow(a,m-2,m)
    
    
    b= copy.copy(A)   
    for i in range(n,r,-1):
        b = (b*i)%m
    
    c = copy.copy(A)
    for i in range(n,n-r,-1):
        c = (c*i)%m
       
    return (a*b*c)%m

def main():
    k = int(input())
    s = input()
    mod = 10**9+7
    z = [1]
    for i in range(1,k+1):
        y = z[-1]*26
        z.append(y%mod)
    l = len(s)

    N = k+2
    inv_t = [0]+[1]
    for i in range(2,N):
        inv_t.append(inv_t[mod % i] * (mod - int(mod / i)) % mod)
    #print(inv_t)
    
    ans = 0
    p = 1   #pow(25,i-len(s),mod)
    #q = z[k]
    bai = 1
    for i in range(l,l+k+1):
        #base = p*q   #pow(26,len(s)+k-i,mod)
        #base = pow(25,i-len(s),mod) * pow(26,len(s)+k-i,mod)
        #bai = r
        #bai = com(i-1,len(s)-1,mod)
        #print(i,len(s),base,bai)
        ans += p*z[l+k-i]*bai
        ans %= mod
        p *= 25
        p %= mod
        #q = z[l+k-i-1]
        bai = bai*i*inv_t[i+1-l]
        bai %= mod
    print(ans)
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    K = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    s=input()
    ls=len(s)
    tot=pow(26,ls+K,mod)
    N=ls+K

    def extgcd1(a0,b0):#計算量log(b0),フェルマーの小定理より早い
        u,v,a,b=1,0,a0,b0
        while b: t=a//b; a-=t*b; a,b=b,a; u,v=v,u-t*v
        if a!=1: return -1#互いに素じゃない
        return u%b0
    
    maxn=N
    fact=[1]*(maxn+1)#NはnCrの最大のn
    ifact=[1]*(maxn+1)
    x=1
    for i in range(2,maxn+1):
        x=(x*i)%mod
        fact[i]=x
        ifact[i]=extgcd1(x,mod)
    

    def comb(n,r): return (fact[n]*ifact[r]%mod)*ifact[n-r]%mod
    
    pows=[pow(25,i,mod) for i in range(N+1)]

    for i in range(0,ls):
        tot-=comb(ls+K,i)*pows[ls+K-i]
        tot%=mod
    print(tot)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

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

def make_tables(n, mod = 10 ** 9 + 7):
    fac = [1, 1] # 階乗テーブル
    finv = [1, 1] #逆元の階乗テーブル
    inv = [0, 1] #逆元テーブル

    for i in range(2, n + 1):
        fac.append((fac[-1] * i) % mod)
        inv.append((mod -inv[mod % i] * (mod // i)) % mod)
        finv.append((finv[-1] * inv[-1]) % mod)
    return fac, finv

def nCk(n, k, mod = 10 ** 9 + 7):
    k = min(k, n-k)
    return fac[n] * finv[k] * finv[n-k] % mod

##########################
fac, finv = make_tables(2*10**6 + 1)
ans = 0
for i in range(k + 1):
    temp = 1
    temp *= pow(26, i, mod)
    temp %= mod
    j = k - i
    if j == 0:
        ans += temp
        continue
    temp *= pow(25, j, mod)
    temp %= mod
    temp *= nCk(n + j - 1, n - 1)
    ans += temp
    ans %= mod
print(ans % mod)

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

k=int(input())
s=list(input())
n=len(s)
mod=10**9+7

g1=[1,1]
g2=[1,1]
inverse=[0,1]

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

pow25=[1]
for i in range(n+k+1):
  pow25.append((pow25[-1]*25)%mod)

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

ans=0
for i in range(n,n+k+1):
  ans+=cmb(i-1,n-1,mod)*pow25[i-n]*pow26[n+k-i]
  ans%=mod
print(ans)

Submission status: Accepted

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


def read():
    K = int(input().strip())
    S = input().strip()
    return K, S


def binom_preprocess(n, MOD=10**9+7):
    f = [0 for i in range(n+1)]  # n!
    invf = [0 for i in range(n+1)]  # (n!)^-1
    f[0] = 1
    f[1] = 1
    invf[0] = 1
    invf[1] = 1
    for i in range(2, n+1):
        f[i] = f[i-1] * i % MOD
    invf[n] = pow(f[n], MOD-2, MOD)
    for i in range(n, 2, -1):
        invf[i-1] = invf[i] * i % MOD
    return f, invf


def binom(n, k, f, invf, MOD=10**9+7):
    if n < k or n < 0 or k < 0:
        return 0
    else:
        return (f[n] * invf[k] % MOD) * invf[n-k] % MOD


def solve(K, S, MOD=10**9+7):
    T = len(S)
    f, invf = binom_preprocess(K+T+1)
    ans = 0
    for i in range(K+1):
        ans += pow(25, i, MOD) * binom(T-1+i, i, f, invf, MOD) * pow(26, K-i, MOD)
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

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

MAX = 2020202
MOD = 10**9 + 7

fac = [0]*MAX
facinv = [0]*MAX
inv = [0]*MAX


def modinv(a, mod):
    b = mod
    x, u = 1, 0
    while b:
        q = a//b
        a, b = b, a-q*b
        x, u = u, x-q*u
    x %= mod
    return x


def mod_nCr_init(n, mod):
    fac[0] = fac[1] = 1
    facinv[0] = facinv[1] = 1
    inv[1] = 1
    for i in range(2, n):
        fac[i] = fac[i-1] * i % mod
        inv[i] = -inv[mod % i] * (mod // i) % mod
        facinv[i] = facinv[i-1] * inv[i] % mod


def mod_nCr(n, r, mod):
    if n < r or n < 0 or r < 0:
        return 0
    return fac[n] * (facinv[r] * facinv[n-r] % mod) % mod


mod_nCr_init(MAX, MOD)

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

print(ans)

Submission status: Accepted

Solution code:
def nCr(n,r,fac,finv):
    mod = (10**9)+7
    ans = fac[n] * (finv[r] * finv[n-r] % mod) % mod
    return ans
k = int(input())
s = input()
l = len(s)
n = l+k+1
# als = list(map(int,input().split()))
# als.sort()
ans = 0
mod = (10**9)+7
fac = [1,1]+[0]*n
finv = [1,1]+[0]*n
inv = [1,1]+[0]*n
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
for i in range(k+1):
    ans += nCr(l-i+k-1,l-1,fac,finv)*pow(26,i,mod)*pow(25,k-i,mod)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
U = 2*10**6+1
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z *= fact_inv[n-k]
    z %= MOD
    return z

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

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    K = int(readline())
    S = readline().strip()

    COM_MAX = 2 * 10 ** 6

    fac, finv, inv = [0] * (COM_MAX + 1), [0] * (COM_MAX + 1), [0] * (COM_MAX + 1)
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

    for i in range(2, COM_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 mod_com(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

    M = len(S)
    L = K + M

    ans = 0
    p = pow(25, K + 1, MOD)
    for i in range(M - 1, -1, -1):
        ans += mod_com(L, i) * p
        p = p * 25 % MOD

    ans = (pow(26, L, MOD) - ans) % MOD
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod=10**9+7
k=int(input())
s=input()
l=len(s)
fact=[1]
for i in range(1,k+l+1):
  fact.append((fact[-1]*i)%mod)
revfact=[]
for i in range(k+l+1):
  revfact.append(pow(fact[i],mod-2,mod))
pow1=[1]
pow2=[1]
for i in range(1,k+l+1):
  pow1.append((pow1[-1]*25)%mod)
  pow2.append((pow2[-1]*26)%mod)
ans=0
for i in range(k+l):
  coef1=(pow1[k-i]*pow2[i])%mod
  if i<=k:
    coef2=(fact[k+l-1-i]*revfact[l-1]*revfact[k-i])%mod
  else:
    coef2=0
  ans+=coef1*coef2
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    K = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    s=input()
    ls=len(s)
    tot=pow(26,ls+K,mod)


    def extgcd1(a0,b0):#計算量log(b0),フェルマーの小定理より早い
            u,v,a,b=1,0,a0,b0
            while b:
                t=a//b; a-=t*b; a,b=b,a; u,v=v,u-t*v
            if a!=1: return -1#互いに素じゃない
            return u%b0
    
    N=ls+K
    fact=[0]*(N+1)#NはnCrの最大のn
    ifact=[0]*(N+1)
    fact[0],fact[1],ifact[0],ifact[1]=1,1,1,1
    for i in range(2,N+1):
        x=(fact[i-1]*i)%mod
        fact[i]=x
        ifact[i]=extgcd1(x,mod)
    pows=[1]*(N+1)
    for i in range(1,N+1):
        pows[i]=pows[i-1]*25%mod

    def comb(n,r): return (fact[n]*ifact[r]%mod)*ifact[n-r]%mod
    
    for i in range(0,ls):
        tot-=comb(ls+K,i)*pows[ls+K-i]
        tot%=mod
    print(tot)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# nCk
## 0!~n!をmodしつつ求める
def fact_all(n,M=mod):
    f = [1]*(n+1)
    ans = 1
    for i in range(1,n+1):
        ans = (ans*i)%M
        f[i] = ans
    return f

## inv(0!)~inv(n!)をmodしつつ求める
def fact_inv_all(fact_all,M=mod):
    N = len(fact_all)
    finv = [0]*N
    finv[-1] = pow(fact_all[-1],M-2,M)
    for i in range(N-1)[::-1]:
        finv[i] = finv[i+1]*(i+1)%M
    return finv

## nCkをmodしつつ返す
def nCk(n,k,fact_list,inv_list,M=mod):
    return (((fact_list[n]*inv_list[k])%M)*inv_list[n-k])%M

K = I()
S = list(input())
N = len(S)

fl = fact_all(N+K+1)
il = fact_inv_all(fl)

beki25 = [1]*(N+K+1)
for i in range(1,N+K+1):
    beki25[i] = beki25[i-1]*25
    beki25[i] %= mod

beki26 = [1]*(N+K+1)
for i in range(1,N+K+1):
    beki26[i] = beki26[i-1]*26
    beki26[i] %= mod

ans = 0
for i in range(N-1,N+K):
    ans += nCk(i,N-1,fl,il)*beki25[i-N+1]*beki26[N+K-1-i]
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

SIZE = 2 * 10 ** 6 + 5
fact = [0] * SIZE
inv = [0] * SIZE
finv = [0] * SIZE
fact[0], fact[1] = 1, 1
inv[1] = 1
finv[0], finv[1] = 1, 1
for i in range(2, SIZE):
    fact[i] = fact[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 < 0 or r < 0 or n < r:
        return 0
    return fact[n] * (finv[r] * finv[n - r] % mod) % mod


k = int(input())
S = input()
s_length = len(S)
full_length = len(S) + k
ans = 0
for i in range(k+1):
    add = pow(26, i, mod) * pow(25, k-i, mod) * nCr(full_length-i-1, s_length-1) % mod
    ans = (ans + add) % mod

print(ans)

Submission status: Accepted

Solution code:
class Factorial():
    def __init__(self, n, mod):
        self.mod = mod
        self.fct = [0 for _ in range(n + 1)]
        self.inv = [0 for _ in range(n + 1)]
        self.fct[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.fct[i + 1] = self.fct[i] * (i + 1) % mod
        self.inv[n] = pow(self.fct[n], mod - 2, mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i + 1] * (i + 1) % mod
            
    def comb(self, m, k):
        if m < k: return 0
        return self.fct[m] * self.inv[k] * self.inv[m - k] % self.mod

MOD = 1000000007
K = int(input())
S = len(input())
F = Factorial(K + S + 1, MOD)
res = 0
for i in range(S, K + S + 1):
    res += F.comb(K + S, i) * pow(25, K + S - i, MOD)
    res %= MOD
print(res)

Submission status: Accepted

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

MAX = 2 * 10**6 + 5
fact = [1] * (MAX + 1)  # i!
finv = [1] * (MAX + 1)  # (i!)^{-1}
iinv = [1] * (MAX + 1)  # i^{-1}
for i in range(2, MAX + 1):
    fact[i] = fact[i - 1] * i % MOD
    iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * iinv[i] % MOD


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


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

print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces

# 大きい数用


import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces

# 大きい数用


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 + 5  # 出力の制限
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

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


K = ni()
S = ns()
s_len = len(S)
mod = 10 ** 9 + 7
ans = 0

total = K + s_len

rui = 1


for i in range(total, s_len - 1, -1):
    ans = (ans + cmb(total, i, mod) * rui) % mod
    # print(ans)
    rui = (rui * 25) % mod
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

k = ni()
s = ns()
n = len(s)
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*3
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(k+1):
    ans += cmb(n-1+i,i,mod)*pow(25,i,mod)%mod*pow(26,k-i,mod)%mod
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
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 = 10 ** 9 + 7
N = 2 * 10 ** 6 + 10 # 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)

k=int(input())
s=input()
lens=len(s)
mod=10**9+7
ans=0

now=1

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

print(ans)

Submission status: Accepted

Solution code:


# def main():
#     n = int(input())
#     al = list(map(int, input().split()))
#     all_xor = 0
#     for a in al:
#         all_xor = all_xor ^ a

#     ans = []
#     for a in al:
#         curr_ans = all_xor ^ a
#         ans.append(curr_ans)

#     print(*ans)


# if __name__ == "__main__":
#     main()


N_MAX = 2*(10**6)
MOD = 10**9 + 7
fac, finv, inv = [0]*N_MAX ,[0]*N_MAX, [0]*N_MAX
def com_init():
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, N_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


def main():
    k = int(input())
    s = input()
    n = len(s)

    com_init()

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

    print(ans%MOD)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
mod = pow(10, 9)+7
k = int(input())
s = input()
n = len(s)
ans = 0
key = pow(26, k, mod)
sub = 1
c = 1
for i in range(k+1):
    ans += key*sub*c
    ans %= mod
    sub *= 25
    sub %= mod
    key = key*pow(26, mod-2, mod)%mod
    c *= (n+i)
    c *= pow(i+1, mod-2, mod)
    c %= mod
print(ans)

Submission status: Accepted

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

mod = 10**9+7 
fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,k+len(s)+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[r]*finv[n-r]%mod
t = len(s)
ans = 0
dp = [0]*(k+1)
dp[0] = 1
ans += pow(26,k)
for i in range(1,k+1):
    x = (nCr(t+i-1,t-1,mod)*pow(25,i,mod))%mod*pow(26,k-i,mod)%mod
    ans += x
    ans %= mod

print(ans%mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter

K = int(input())
S = input().rstrip('\n')

MOD = 10 ** 9 + 7

T = K + len(S)
fac = [1] * (T+1)
for i in range(1, T+1):
	fac[i] = fac[i-1] * i % MOD;

inv = [1] * (T+1)
inv[-1] = pow(fac[-1], MOD-2, MOD)
for i in range(T-1, -1, -1):
	inv[i] = inv[i+1] * (i+1) % MOD

def choose(n, k):
	return fac[n] * inv[n - k] % MOD * inv[k] % MOD

A = 1
l = len(S)
for i in range(K):
	A = A * 26 + pow(25, i+1, MOD) * choose(len(S)+i, i+1)
	A %= MOD

#A = pow(26, len(S)+K, MOD)
#A *= pow(56, MOD-2, MOD)
print(A%MOD)

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

K = ri()
S = rs()

class CombMod:
    def __init__(self, N):
        self.fact = [1]
        self.rfact = [1]
        for i in range(1, N+1):
            self.fact.append(self.fact[i-1]*i % mod)
            self.rfact.append(pow(self.fact[i], mod-2, mod))

    def comb(self, n, k):
        return self.fact[n]*self.rfact[k]*self.rfact[n-k] % mod

class PowMod:
	def __init__(self, N, base=[2]):
		self.mem = {}
		for b in base:
			pows = [1]
			for i in range(1, N+1):
				pows.append(pows[-1]*b % mod)
			self.mem[b] = pows

	def pow(self, b, n):
		return self.mem[b][n]

N = len(S)
cm = CombMod(K+N)
pm = PowMod(K, base=[25, 26])

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 1000000007  # type: int


class Combination(object):

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

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


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

    A = len(S)-1
    cmb = Combination(K+A)
    ans = 0
    for k in range(K+1):
        b = 1
        b *= pow(26, k, MOD)
        b %= MOD
        b *= pow(25, K-k, MOD)
        b %= MOD
        b *= cmb(K-k+A, A)
        # print(cmb(K-k+A, A))
        b %= MOD
        ans += b
        ans %= MOD
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

K = int(input())
S = str(input())
mod = 10**9+7
lens = len(S)
length = lens+K

L = 1
pow_dic = [0]*(10**6*2+1)
pow_dic[0] = 1
for i in range(1, 10**6*2+1):
    L = L*i%mod
    pow_dic[i] = L%mod
ans = 0
for rest in range(K+1):
    lenall = length-rest-1
    nlens = lens-1
    l = pow_dic[lenall]*pow(pow_dic[lenall-nlens], mod-2, mod)%mod
    r = pow_dic[nlens]
    comb = l*pow(r, mod-2, mod)%mod
    ans += pow(25, K-rest, mod)*pow(26, rest, mod)*comb%mod
    ans %= mod
print(ans%mod)

Submission status: Accepted

Solution code:
import numpy as np
import numba

@numba.njit("i8(i8,i8,i8)", cache=True)
def pow_numba(a, r, mod):
    r %= (mod-1)
    res = 1
    while r:
        if r%2:
            res = res * a % mod
        a = a * a % mod
        r //= 2
    return res

@numba.njit("UniTuple(i8,3)(i8,i8)", cache=True)
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

@numba.njit("UniTuple(i8[:],2)(i8,i8)", cache=True)
def get_table(mod, n_max):
    f = 1
    fac = [f]
    for i in range(1, n_max+1):
        f = f * i % mod
        fac.append(f)
    #f = egcd(f, mod)[1] % mod
    f = pow_numba(f, -1, mod)
    facinv = [f]
    for i in range(n_max, 0, -1):
        f = f * i % mod
        facinv.append(f)
    facinv.reverse()
    return np.array(fac), np.array(facinv)

@numba.njit("i8(i8,i8)", cache=True)
def solve(K, N):
    mod = 10**9+7
    fac, facinv = get_table(mod, 2020202)
    ans = 0
    for i in range(K+1):
        a = fac[N+K-1-i] * facinv[N-1] % mod * facinv[K-i] % mod
        a = a * pow_numba(25, K-i, mod) % mod * pow_numba(26, i, mod) % mod
        ans += a
    return ans % mod

K = int(input())
S = input()
N = len(S)
print(solve(K, N))