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 examA():
    S = SI()
    if S in alphabet:
        ans = "a"
    else:
        ans = "A"
    print(ans)
    return

def examB():
    N, K = LI()
    P = LI()
    P.sort()
    ans = sum(P[:K])
    print(ans)
    return

def examC():
    N = I()
    ans = ""
    while(N>0):
        N -= 1
        ans += alphabet[N%26]
        N //= 26
        if N==0:
            break
    print(ans[::-1])
    return

def examD():
    N = I()
    A = LI()
    D = defaultdict(int)
    for a in A:
        D[a] += 1
    S = sum(A)
    q = I()
    ans = [0]*q
    for i in range(q):
        a, b = LI()
        if not a in D:
            ans[i] = S
            continue
        S += (b-a)*D[a]
        D[b] += D[a]
        D[a] = 0
        ans[i] = S

    for v in ans:
        print(v)
    return

def examE():
    N = I()
    A = LI()
    S = 0
    for a in A:
        S ^= a
    #print(S)
    ans = [0]*N
    for i in range(N):
        ans[i] = S^A[i]
    print(" ".join(map(str,ans)))
    return

def examF():
    class combination():
        # 素数のmod取るときのみ　速い
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

            self.inv[n] = pow(self.fac[n], mod - 2, mod)
            for j in range(n - 1, -1, -1):
                self.inv[j] = self.inv[j + 1] * (j + 1) % mod

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

    K = I()
    S = SI()
    N = len(S) + K
    C = combination(N,mod)
    P = [1]*(K+1)
    for i in range(K):
        P[i+1] = P[i]*26%mod
    v = 0
    prev = S[0]
    for s in S[1:]:
        if prev!=s:
            v += 1
            prev = s
    v = len(S)-1
    cnt = 0
    #print(v)
    for i in range(K+1):
        if i%2==0:
            cnt += C.comb(N,N-K+i)*P[K-i]*C.comb(v+i,v)
            cnt %= mod
        else:
            cnt -= C.comb(N,N-K+i)*P[K-i]*C.comb(v+i,v)
            cnt += mod**3
            cnt %= mod
        #print(C.comb(v+i,v))
        #print(P[K-i])
        #print(cnt)
        #if i==K:
            #print(C.comb(N,N-K+i)*P[K-i]*C.comb(v+i,v))

    ans = cnt
    print(ans)
    return

def examF2():
    class combination():
        # 素数のmod取るときのみ　速い
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

            self.inv[n] = pow(self.fac[n], mod - 2, mod)
            for j in range(n - 1, -1, -1):
                self.inv[j] = self.inv[j + 1] * (j + 1) % mod

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

    K = I()
    S = SI()
    N = len(S) + K
    C = combination(N,mod)
    P = [1]*(K+1)
    for i in range(K):
        P[i+1] = P[i]*25%mod
    v = 0
    prev = S[0]
    for s in S[1:]:
        if prev!=s:
            v += 1
            prev = s
    cnt = 0
    cnt = P[K]*C.comb(N,K)
    #cnt %= mod
    ans = cnt
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
"""

部分文字列にSを含む長さ|S|+Kの文字列の数
dp[i][j] = i文字目まで見てj文字目まで含んでる文字列の数
dp[i][j] = dp[i-1][j] * 25 + dp[i-1][j-1]

dp[0][0] = 1
dp[|S|+K][|S|]が欲しい

1に
1かける/25を掛ける
をそれぞれ |S|回、K回やった組み合わせの総和


"""
def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる)

    return fac[n] * inv[n-r] * inv[r] % mod

K = int(input())

S = input()
ls = len(S)

mod = 10**9+7

fac,inv = modfac(3*(10**6),mod)

ans = 0

for i in range(ls,ls+K+1):
    down = i-ls
    rem = K-down
    #print (down,rem)
    now = pow(26,rem,mod) * pow(25,down,mod) * modnCr(i-1,ls-1,mod,fac,inv) % mod
    #print (i,now)
    ans += now
    ans %= mod
#print ( * modnCr(ls+K,K,mod,fac,inv) % mod)
print (ans % mod)

Submission status: Accepted

Solution code:
class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0



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

N = K + s

MOD = 10 ** 9 + 7

C = Factorial(N + 10, MOD)

lst26 = [1] * (K + 2)
lst25 = [1] * (K + 2)
for i in range(K + 1):
    lst26[i + 1] = (lst26[i] * 26) % MOD
    lst25[i + 1] = (lst25[i] * 25) % MOD

ans = 0
for x in range(K + 1):
    tmp = ((C.factorial(s - 1 + K - x) * C.ifactorial(s - 1)) % MOD) * C.ifactorial(K - x)
    tmp %= MOD
    tmp = (tmp * lst26[x]) % MOD
    tmp = (tmp * lst25[K - x]) % MOD
    ans = (ans + tmp) % 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

# 大きい数用


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

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

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

total = K + s_len

rui = 1

cmb = 1

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

Submission status: Accepted

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

mod = 10 ** 9 + 7

N = len(S) + K

power = [1]
fac = [1]
inv = [1]
for i in range(1, N + 10) :
  power.append(power[-1] * 25 % mod)
  fac.append(fac[-1] * i % mod)
  
inv = [pow(fac[-1], mod - 2, mod)]
for i in range(N + 10 - 1, 0, -1) :
  inv.append(inv[-1] * i % mod)
inv = inv[::-1]

def comb(n, r) :
  if r == 0 :
    return 1
  return fac[n] * inv[n - r] * inv[r] % mod
  
ret = pow(26, N, mod)
for i in range(len(S)) :
  ret -= power[N - i] * comb(N, i) % mod
  ret %= mod
  
print(ret)

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    k = int(ipt())
    s = input()
    ls = len(s)
    mod = 10**9+7
    #nCrをmodで割った余りを求める。Nに最大値を入れて使用。
    N = 2*10**6
    g1 = [1, 1] # 元テーブル
    g2 = [1, 1] #逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル
    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
    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
    s25 = [1]
    s26 = [1]
    for i in range(k+1):
        s25.append(s25[-1]*25%mod)
        s26.append(s26[-1]*26%mod)

    for i in range(ls):
        ans = (ans+s25[k]*cmb(k+i-1,i,mod)%mod)%mod
    for i in range(1,k+1):
        ans = (ans+s25[k-i]*s26[i]%mod*cmb(k+ls-1-i,ls-1,mod)%mod)%mod
    print(ans)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import reduce
def comb(n, max_k, mod):
    """
    (n,k) := n個からk個選ぶ組み合わせ
    k = 0~max_Kまでを計算して返す
    """
    res = [1]*(max_k+1)
    t = 1
    for i in range(max_k+1):
        res[i] *= t
        t *= n-i
        t %= mod

    n = reduce(lambda x,y: (x*y)%mod, range(1,max_k+1), 1)
    n = pow(n,-1, mod)

    for i in reversed(range(max_k+1)):
        res[i] *= n
        res[i] %= mod
        n *= i
        n %= mod
    return res

MOD = 10**9+7

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

res = 0
x = 1

com = comb(N+K, K, MOD)

for c in com:
    res += x*c
    res %= MOD
    x *= 25
    x %= MOD

print(res)

Submission status: Accepted

Solution code:
K=int(input())
S=input()
n=K+len(S)
MAX=2000000
fac=[0]*MAX
finv=[0]*MAX
inv=[0]*MAX
MOD=10**9+7
#テーブルを作る前処理
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 comb(n,k):
  if (n < k):
    return 0
  if (n < 0 or k < 0):
    return 0
  else:
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

COMinit()
com=1
q=(26**K)%(10**9+7)
ans=0
for i in range(K+1):
  ans+=(q*comb(len(S)+i-1,i))%(10**9+7)#comb(len(S)+i-1,len(S)-1))%(10**9+7)
  q=(q*423076927)%(10**9+7)
  #com=(com*(len(S)+i))//(i+1)
print(ans%(10**9+7))
#print((25*576923081)%(10**9+7))

Submission status: Accepted

Solution code:
mod = 10**9+7
M = 2*10**6

def main(K,S):
    fact = [1]*(M+1)
    factinv = [1]*(M+1)
    for n in range(1,M+1):
        fact[n] = n*fact[n-1]%mod
        factinv[n] = pow(fact[n],mod-2,mod)

    def comb(n,k):
        return fact[n]*factinv[k]*factinv[n-k]%mod
    n = len(S)
    ans = 0

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

if __name__ == '__main__':
    K = int(input())
    S = input()
    main(K,S)

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
size = 2*10**6
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, size + 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()
L1 = [1]
L2 = [1]
for _ in range(10 ** 6):
    L1.append(L1[-1] * 25 % mod)
    L2.append(L2[-1] * 26 % mod)

ans = 0
for i in range(K+1):
    ans += L1[K-i] * L2[i] * cmb(K - i + len(S) - 1, len(S) - 1, mod)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
k=int(input())
s=input().rstrip()
INF=10**9+7
ans=0
n=len(s)
def modinv(a,m):
    b=m
    (x,lastx)=(0,1)
    (y,lasty)=(1,0)
    while not b==0:
        q=a//b
        (a,b)=(b,a%b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx%m

x=26**k
y=modinv(26,INF)
c=1

for i in range(k+1):
    ans=(ans+c*x)%INF
    x=(x*25*y)%INF
    c=(c*(n+i)*modinv(i+1,INF))%INF

print(ans)

Submission status: Accepted

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

mod = 10**9+7

m = 2*10**6 +10 
fac = [1]*m
ninv = [1]*m
finv = [1]*m
for i in range(2,m):
    fac[i] = fac[i-1]*i%mod
    ninv[i] = (-(mod//i)*ninv[mod%i])%mod
    finv[i] = finv[i-1]*ninv[i]%mod

def comb(n,k):
    return (fac[n]*finv[k]%mod)*finv[n-k]%mod

N = len(S)
ans = 0

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

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 = 2000005
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 = len(input())
ans = 0
for i in range(S, S + K + 1):
    ans += cmb(S + K, i, mod) * pow(25, K + S - i, mod)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

k = int(input())
n = len(input())
s = n + k

comb_s = [1]
rest = pow(25, s, MOD)
for i in range(1, n):
    comb_s.append(comb_s[-1] * (s+1-i) * pow(i, MOD-2, MOD) % MOD)
    rest += pow(25, s-i, MOD) * comb_s[i]

print((pow(26, s, MOD) - rest) % MOD)

Submission status: Accepted

Solution code:
n = 2 * (10**6) + 10
mod = 10 ** 9 + 7
fact = [1]*(n+1)
rfact = [1]*(n+1)
r = 1
for i in range(1, n+1):
  fact[i] = r = r * i % mod
rfact[n] = r = pow(fact[n], mod-2, mod)
for i in range(n, 0, -1):
  rfact[i-1] = r = r * i % mod

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % mod

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % mod

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

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

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


class combination():
    def __init__(self, mod):
        '''
        modを指定して初期化
        '''
        self.mod = mod
        self.fac = [1, 1]  # 階乗テーブル
        self.ifac = [1, 1]  # 階乗の逆元テーブル
        self.inv = [0, 1]  # 逆元計算用

    def calc(self, n, k):
        '''
        nCk%modを計算する
        '''
        if k < 0 or n < k:
            return 0
        self.make_tables(n)  # テーブル作成
        k = min(k, n - k)
        return self.fac[n] * (self.ifac[k] * self.ifac[n - k] %
                              self.mod) % self.mod

    def make_tables(self, n):
        '''
        階乗テーブル・階乗の逆元テーブルを作成
        '''
        for i in range(len(self.fac), n + 1):
            self.fac.append((self.fac[-1] * i) % self.mod)
            self.inv.append(
                (-self.inv[self.mod % i] * (self.mod // i)) % self.mod)
            self.ifac.append((self.ifac[-1] * self.inv[-1]) % self.mod)


k = inp()
s = str_inp()
comb = combination(mod)
ans = pow(26, len(s) + k, mod)
for i in range(0, len(s)):
    ans -= comb.calc(k + len(s), i) * pow(25, k + len(s) - i, mod)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
def inv_mod(a, p):
    p = abs(p)
    a %= p
    stack = []
    p0 = p
    while a > 1:
        d, a, p = p//a, p%a, a
        stack.append(d)
    x, y = 1, 0
    while stack:
        d = stack.pop()
        x, y = y-d*x, x
    return x % p0

def comb_mod(n,k,p):
    ans = 1
    k = min(k,n-k)
    if k < 0:
        return 0
    for i in range(k):
        ans = ans * (n-i) * inv_mod(k-i,p) % p
    return ans

MOD = 10**9 + 7
K = int(input())
N = len(input())
f = 26 * inv_mod(25, MOD) % MOD
a = pow(25, K, MOD) * comb_mod(N+K-1, N-1, MOD)
ans = 0
for r in range(K+1):
    ans = (ans + a) % MOD
    a *= (f * (K-r) * inv_mod(N+K-r-1, MOD))
    a %= MOD
print(ans)

Submission status: Accepted

Solution code:
class Combination:
    """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""
    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
        self.MOD = MOD

    def inverse(self, k):
        """kの逆元を求める O(1)"""
        return (self.inv_fact[k] * self.fact[k - 1]) % self.MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD

    def combination2(self, k, r):
        """kCrを求める O(r)
        kが大きいが、r <= nを満たしているときに使用
        """
        if k < r:
            return 0
        res = 1
        for l in range(r):
            res *= (k - l)
            res %= self.MOD
        return (res * self.inv_fact[r]) % self.MOD


k = int(input())
s = input()
MOD = 10 ** 9 + 7
comb = Combination(2 * 10 ** 6, MOD)

ans = 0

box = len(s)
for top in range(k + 1):
    ptn = pow(26, top, MOD)
    
    ball = k - top
    ptn *= comb.combination(ball + box - 1, ball) 
    ptn %= MOD
    ptn *= pow(25, ball, MOD)
    ptn %= MOD
    ans += ptn
    ans %= MOD
print(ans % MOD)

Submission status: Accepted

Solution code:
mod = 10**9+7
rng = 2000100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0 or n<k:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
k = int(input())
s = input()
n = len(s)
ans = pow(26,n+k,mod)
for i in range(n):
  ans -= pow(25,n+k-i,mod)*cmb(n+k,i)
  ans %= mod
print(ans)

Submission status: Accepted

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

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 = N+K
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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


ans = cmb(N+K-1, K, mod)*pow(25, K, mod)%mod

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

print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
list_size = 2000001

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size-1):
	f_list[i+1] = (f_list[i] * (i+1)) % MOD

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(list_size-2, -1, -1):
	f_r_list[i] = (f_r_list[i+1] * (i+1)) % MOD

def comb(n, r):
	if n < r or r < 0:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (f_list[n] * f_r_list[n-r] * f_r_list[r]) % MOD 

k = int(input())
s = input()
n = len(s)
ps = [1]
for i in range(k+1):
	ps.append((ps[-1] * 25) % MOD)
ans = 0
for i in range(k+1):
	ans += comb(n+k, i) * ps[i]
	ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7
MAXN = 2*10**6+5
f = [1]
for i in range(MAXN):
    f.append(f[-1] * (i+1) % MOD)
def nCr(n, r, mod=MOD):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod

K = int(input())
S = input()
R = len(S)
N = K + R
ans = 0
for r in range(R,N+1):
    power = pow(25, N-r, MOD)
    ans += nCr(N, r) * power % MOD
    ans %= MOD
print(ans)

Submission status: Accepted

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

M = 2*10**6
fact = [1]*(M+1)
factinv = [1]*(M+1)
for n in range(1,M+1):
    fact[n] = n*fact[n-1]%mod
    factinv[n] = pow(fact[n],mod-2,mod)

def comb(n,k):
    return fact[n]*factinv[k]*factinv[n-k]%mod
n = len(S)
ans = 0

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

Submission status: Accepted

Solution code:
from numba import njit
import numpy as np


@njit('i8(i8, i8, i8)', cache=True)
def mod_pow(x, a, MOD):
    ret = 1
    cur = x
    while a:
        if a & 1:
            ret = ret * cur % MOD
        cur = cur * cur % MOD
        a >>= 1
    return ret


@njit('UniTuple(i8[:], 2)(i8, i8)', cache=True)
def prepare(n, MOD):
    factorials = np.ones(n + 1, dtype=np.int64)
    for i in range(2, n + 1):
        factorials[i] = factorials[i - 1] * i % MOD
    finvs = np.ones(n + 1, dtype=np.int64)
    finvs[n] = mod_pow(factorials[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        finvs[i - 1] = finvs[i] * i % MOD
    return factorials, finvs


@njit('i8(i8, i8)', cache=True)
def solve(k, ls):
    MOD = 10 ** 9 + 7
    facts, finvs = prepare(k + ls, MOD)

    ans = 0
    for i in range(k + 1):
        r = k - i
        pat = facts[ls + r - 1] * finvs[ls - 1] % MOD * finvs[r] % MOD
        ans = (ans + pat * mod_pow(25, r, MOD) % MOD * mod_pow(26, i, MOD)) % MOD

    return ans


k = int(input())
s = input()
print(solve(k, len(s)))

Submission status: Accepted

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

fact = [1] * (n + 1)
revfact = [1] * (n + 1)
for i in range(n):
    fact[i + 1] = ((i + 1) * fact[i]) % mod
revfact[n] = pow(fact[n], mod - 2, mod)
for i in reversed(range(n)):
    revfact[i] = ((i + 1) * revfact[i + 1]) % mod
def combination(n, k, p):
    return (fact[n] * revfact[k] * revfact[n - k]) % p

ans = 0
comb = []
tf = [1]
for i in range(n + 1):
    comb.append(combination(n, i, mod))
    tf.append(tf[-1] * 25 % mod)
del tf[-1]
tf.reverse()
for i in range(len(s), n + 1):
    ans += comb[i] * tf[i]
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n):
    res = [None] * n
    for i in range(n):
        res[i] = II()
    return res
def LIR(n):
    res = [None] * n
    for i in range(n):
        res[i] = LI()
    return res
def FR(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
def LFR(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
def LIR_(n):
    res = [None] * n
    for i in range(n):
        res[i] = LI_()
    return res
def SR(n):
    res = [None] * n
    for i in range(n):
        res[i] = S()
    return res
def LSR(n):
    res = [None] * n
    for i in range(n):
        res[i] = LS()
    return res
mod = 1000000007
inf = float('INF')
fact = [i for i in range(2 * 10 ** 6 + 1)]
fact[0] = 1
for i in range(2 * 10 ** 6):
    fact[i + 1] *= fact[i]
    fact[i + 1] %= mod
invfact = fact[:]
invfact[-1] = pow(invfact[-1], mod - 2, mod)
for i in range(2 * 10 ** 6, 0, -1):
    invfact[i - 1] = i * invfact[i]
    invfact[i - 1] %= mod

def combination_mod(n, k, mod):
    """ power_funcを用いて(nCk) mod p を求める """ 
    """ nCk = n!/((n-k)!k!)を使用 """
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    a = fact[n]
    b = invfact[k]
    c = invfact[n - k]
    return (a * b * c) % mod

#solve
def solve():
    k = II()
    s = S()
    ans = pow(26, len(s) + k, mod)
    sk = len(s) + k
    for i in range(len(s)):
        ans -= combination_mod(sk, i, mod) * pow(25, sk - i, mod)
        ans %= mod
    print(ans)
    return


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

Submission status: Accepted

Solution code:
K=int(input())
S = input()
MOD = 10**9+7
val1 = len(S)+K
val2 = len(S)
# dp = [[0]*(val2+1) for _ in range(val1+1)]
# dp[0][0] = 1
# for i in range(val1):
#     for j in range(val2+1):
#         if j==val2-1:
#             dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * 26) % MOD
#         else:
#             dp[i+1][j] = (dp[i+1][j] + dp[i][j]*25)%MOD
#     for j in range(val2):
#         dp[i+1][j+1] = (dp[i+1][j+1]+dp[i][j])%MOD
# print(dp[val1][val2])
# print(dp)

N = val1
fact = [1]*2 + [0]*(N-1)
ifact = [1]*2 + [0]*(N-1)
inv = [0,1] + [0]*(N-1)
p=10**9+7

for i in range(2,N+1):
    fact[i] = (fact[i-1]*i)%p
    inv[i] = p - inv[p%i]*(p//i)%p
    ifact[i] = (ifact[i-1]*inv[i])%p
def op(n,k):
    if k<0 or k>n or n<0:
        return 0
    return (fact[n]*ifact[k]*ifact[n-k])%p

res = 0
for i in range(K+1):
    tmp = pow(26,K-i,MOD) * pow(25,i,MOD) * op(val2+i-1,i)
    res = (res + tmp)%MOD
print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
K = I()
S = S()
N = len(S)

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

Submission status: Accepted

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

m = [1]*(k+1)
M = [1]*(k+1)
h = [1]*(k+1)
for i in range(k):
    m[i+1] = (m[i] * 25)%mod
    M[i+1] = (M[i] * 26)%mod
    h[i+1] = (h[i]*(n+i)*pow(i+1,mod-2,mod))%mod

ans = 0
for i in range(k+1):
    ans += m[i]*M[k-i]%mod*h[i]%mod
    ans %= mod
print(ans)

Submission status: Accepted

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

FACT=[1]
for i in range(1,2*10**6+3):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**6+2,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0


LEN=len(S)
ANS=0
for i in range(K+1):
    ANS+=Combi(i+LEN-1,LEN-1)*pow(25,i,mod)*pow(26,K-i,mod)
print(ANS%mod)