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, 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

N = len(S)
cm = CombMod(K+N)

pows = [1]
pows2 = [1]
p = 1
p2 = 1
for i in range(K+1):
	p = (p * 25) % mod
	p2 = (p2 * 26) % mod
	pows.append(p)
	pows2.append(p2)
#print(pows)
ans = 0
for i in range(K+1):
	#ans += cm.comb(K+N-i-1, N-1) * pow(26, i, mod) * pow(25, K-i, mod)
	ans += cm.comb(K+N-i-1, N-1) * pows2[i] * pows[K-i]
	ans = ans % mod
print(ans)

Submission status: Accepted

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

mod = 10**9 + 7
K = int(input())
S = input().rstrip()

N = K + len(S)
fact = [1] * (N+1)
fact_inv = [1] * (N+1)
for i in range(1, N+1):
    fact[i] = i * fact[i-1] % mod
fact_inv[N] = pow(fact[N], mod-2, mod)
for i in range(1, N+1)[::-1]:
    fact_inv[i-1] = i * fact_inv[i] % mod
comb = lambda n, k: fact[n] * fact_inv[k] * fact_inv[n-k] % mod

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

Submission status: Accepted

Solution code:
def comb_mod(n,r,mod):
    ans = 1
    lis = []
    for i in range(r):
        ans *= n+i
        ans *= pow(i+1,mod-2,mod)
        ans %= mod
        lis.append(ans)
    return lis
def solve():
    ans = 1
    mod = 10**9+7
    K = int(input())
    S = input()
    s = len(S)
    lis = comb_mod(s,K,mod)
    for k in range(K):
        ans *= 26
        ans += lis[k]*pow(25,k+1,mod)
        ans %= mod
    return ans
print(solve())

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

n_ = 2 * 10**6 + 5
mod = 10**9 + 7
fun = [1] * (n_ + 1)
for i in range(1, n_ + 1):
    fun[i] = fun[i - 1] * i % mod
rev = [1] * (n_ + 1)
rev[n_] = pow(fun[n_], mod - 2, mod)
for i in range(n_ - 1, 0, -1):
    rev[i] = rev[i + 1] * (i + 1) % mod

def nCr(n, r):
    if r > n:
        return 0
    return fun[n] * rev[r] % mod * rev[n - r] % mod

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


inv26 = modinv(26, mod)


def solve():
    k = ni()
    s = ns()
    n = len(s)
    ans = 0
    v = 1
    u = pow(26, k, mod)
    for i in range(n, n+k+1):
        ans = (ans + nCr(i-1, n-1) * v * u) % mod
        u = u * inv26 % mod
        v = v * 25 % mod
    print(ans)
    return

solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
K = int(input())
S = list(input())[: -1]
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(10 ** 6 * 3, mod)
res = 0
for i in range(K + 1):
  #i ko migi soto
  t = f.combi(len(S) - 1 + K - i, len(S) - 1) * pow(25, K - i, mod) % mod
  t = t * pow(26, i, mod) % mod
  res += t
  res %= mod
print(res)

Submission status: Accepted

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

mod = 10**9 + 7

## nCkのmodを求める関数
# テーブルを作る(前処理)
max = 2 * 10**6 + 100
fac, finv, inv = [0]*max, [0]*max, [0]*max

def comInit(max):
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

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

comInit(max)

# 二項係数の計算
def com(n,k):
    if(n < k):
        return 0
    if( (n<0) | (k < 0)):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

ans = 0
ex25 = [1] * (k+1)
ex26 = [1] * (k+1)
for i in range(1,k+1):
    ex25[i] = (ex25[i-1] * 25)%mod
    ex26[i] = (ex26[i-1] * 26)%mod

for i in range(k+1):
    j = k-i
    tmp = ex25[i] * com(n+i-1,i) * ex26[j]
    ans = (ans+tmp)%mod

print(ans)

Submission status: Accepted

Solution code:
M = 10 ** 9 + 7

# inverse
def calc_inverse(n, law):
	if n == 1:
		return 1
	
	pre_r = law
	pre_x = 0
	pre_y = 1
	cur_r = n
	cur_x = 1
	cur_y = 0
	
	while True:
		d = pre_r // cur_r
		r = pre_r % cur_r
		
		nxt_r = r
		nxt_x = pre_x - d * cur_x
		nxt_y = pre_y - d * cur_y
		
		if nxt_r == 1:
			ret = nxt_x
			while ret < 0:
				ret += law;
			return ret;
		elif nxt_r == 0:
			return None
		
		pre_r = cur_r;
		pre_x = cur_x;
		pre_y = cur_y;
		cur_r = nxt_r;
		cur_x = nxt_x;
		cur_y = nxt_y;

facts = [1]
facts_i = [1]
def cache_facts(n, M):
	f = 1
	fi = 1
	for i in range(1, n):
		f = (f * i) % M
		fi = (fi * calc_inverse(i, M)) % M
		facts.append(f)
		facts_i.append(fi)

def cached_C(a, b, M):
	return facts[a] * facts_i[a - b] * facts_i[b] % M

K = int(input())
S = input().strip()
L = len(S)

cache_facts(K + L + 1, M)

total = pow(26, K, M)

#print(total)
for i in range(1, K + 1):
	total = (total + (pow(25, i, M) * cached_C(L + i - 1, L - 1, M) % M) * pow(26, K - i, M)) % M

print(total)

Submission status: Accepted

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

P = 10 ** 9 + 7
def mod_prod(a,b):
    return (a % P) * (b % P) % P

def mod_fact(a):
    ret = 1
    for i in range(a):
        ret = ret * (i + 1) % P
    return ret

def mod_pow(a, n):
    ret = 1
    while n > 0:
        if n % 2 == 1:
            ret = ret * a % P
        a = a * a % P
        n = n >> 1
    return ret

def mod_div(a, b):
    b_inv = mod_pow(b, P - 2)
    return a * b_inv % P

def mod_comb(a,b):
    ret = 1
    b = min(b, a - b)
    for i in range(b):
        ret *= a - i
        ret %= P
    ret = mod_div(ret, mod_fact(b))
    return ret

def solve():
    K = int(readline())
    S = readline().rstrip()

    N = len(S)

    ans = 0
    cb = 1
    for i in range(K + 1):
        ans += mod_pow(25, i) * cb * mod_pow(26, K-i)
        cb = cb * mod_div(i + N - 1 + 1, i + 1) % P
        # mod_comb(i+N-1, i)
        ans %= P
    print(ans)

solve()

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()

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

print(ans%mod)

Submission status: Accepted

Solution code:
import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def nCr(com_n, com_r):
    if com_n < com_r: return 0
    return fac[com_n] * ifac[com_r] % md * ifac[com_n - com_r] % md

# combinationの準備
# md>n_maxの条件
md = 10 ** 9 + 7
n_max = 2000005
fac = [1]
for i in range(1, n_max + 1): fac.append(fac[-1] * i % md)
ifac = [1] * (n_max + 1)
ifac[n_max] = pow(fac[n_max], md - 2, md)
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1) % md

def main():
    k=II()
    s=SI()
    r=len(s)
    ans=0
    for i in range(k+1):
        ans=ans*26+pow(25,i,md)*nCr(i+r-1,r-1)%md
        ans%=md
    print(ans)

main()

Submission status: Accepted

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

mod = 10**9+7
N = K+S

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

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

answer = 0
pow = -1
for i in range(K+1):
    if pow == -1:
        pow = 1
    else:
        pow = (pow*25)%mod
    answer = (answer+pow*factorial_inv[i]*factorial_inv[N-i])%mod
answer = (answer*factorial)%mod
print(answer)

Submission status: Accepted

Solution code:
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class Combination(object):
	def __init__(self, N, con):
		self.fac = [0] * (N + 1)
		self.inv = [0] * (N + 1)
		self.finv = [0] * (N + 1)
		self.fac[0], self.fac[1] = 1, 1
		self.inv[1] = 1
		self.finv[0], self.finv[1] = 1, 1

		# 前計算
		for i in range(2, N + 1):
			self.fac[i] = self.fac[i - 1] * i % con
			self.inv[i] = self.inv[con % i] * (con - (con // i)) % con
			self.finv[i] = self.finv[i - 1] * self.inv[i] % con

	def com(self, N, k):
		return (self.fac[N] * self.finv[k] * self.finv[N - k]) % con


#処理内容
def main():
	K = int(input())
	S = list(input())
	N = len(S)
	C = Combination(N + K, con)
	ans = pow(26, K + N, con)
	for i in range(N):
		ans -= C.com(N + K, i) * pow(25, K + N - i, con)
		ans %= con

	print(ans)



if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
mod=10**9+7
f=[1]
for i in range(2*10**6+7):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod
k=int(input())
s=input()
n=len(s)
ans=0
for i in range(k,-1,-1):
  ans+=comb(n+k,i)*pow(25,i,mod)
  ans%=mod
print(ans%mod)

Submission status: Accepted

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


def inv(a, mod):
    r = [1, 0, a]
    w = [0, 1, mod]
    while w[2] != 1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = w
        w = r_new
    x, y = w[0], w[1]    # a*x+y*mod = 1
    return (mod+x % mod) % mod


max_num = 2*10**6+1
fact = [0 for _ in range(max_num)]
ifact = [0 for _ in range(max_num)]

fact[0] = fact[1] = 1
ifact[0] = ifact[1] = 1

for i in range(2, max_num):
    fact[i] = fact[i-1] * i % mod

ifact[max_num-1] = inv(fact[max_num-1], mod)

for i in range(2, max_num):
    ifact[max_num-i] = (ifact[max_num-i+1] * (max_num-i+1)) % mod


def comb(x, y):
    if x < 0 or y < 0 or x < y:
        return 0
    else:
        return fact[x] * ifact[y] * ifact[x-y] % mod


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

ans = 0
for i in range(k+1):
    tmp = comb(n-1+i, i)*pow25[i]
    tmp %= mod
    tmp *= pow26[k-i]
    tmp %= mod
    ans += tmp
    # ans += comb(n-1+i, i)*pow(25, i, mod)*pow(26, k-i, mod)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys, math
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int
def calc_fraction_mod(numerator, denominator):
    '''
        returns numerator / denominator (mod MOD)
    '''
    inv = pow(denominator, MOD - 2, MOD)
    return numerator * inv % MOD

def make_facts(n):
    '''
        make factorials
        0!(=1), 1!, 2!, 3! .... n!
    '''
    fact = [1]
    for i in range(n):
        fact.append((fact[i] * (i + 1)) % MOD)
    return fact


def make_combs(n, k):
    '''
        make [C(n - k, 0), C(n - k + 1, 1), C(n, 2) ..... C(n, k)]
    '''
    facts = make_facts(n)
    invs = [] # inverted for fraction
    for fact in facts:
        invs.append(pow(fact, MOD - 2, MOD))

    ret = []
    for i in range(0, k + 1):
        x = n - k + i
        a = facts[x]
        #b = facts[i]
        #c = facts[n - i]
        #ret.append(calc_fraction_mod(a, b))
        ret.append(a * invs[i] * invs[x - i] % MOD)
    return ret

def solve(K: int, S: str):
    n = len(S)
    N = K + n
    ret = 0
    p26 = [1]
    p25 = [1]
    for i in range(1, K + 1):
        #p26.append(pow(26, i, MOD))
        #p25.append(pow(25, i, MOD))
        p26.append(p26[-1] * 26 % MOD)
        p25.append(p25[-1] * 25 % MOD)
    coms = make_combs(N - 1, K)
    #print('a')
    #print('b')
    for i in range(K + 1):
        #tmp = p26[i] * p25[K - i] * c(N - i - 1, K - i)
        tmp = p26[i] * p25[K - i] * coms[K - i]
        #print(i, p26[i], p25[K - i], coms[K - i], tmp)
        ret += tmp
        ret %= MOD
    print(ret)
    return


def solve_(K: int, S: str):
    n = len(S)
    N = K + n
    coms = make_combs(N, n)
    ret = pow(26, N, MOD)
    tmp = pow(25, coms[n], MOD)
    print(coms[n], ret, tmp)
    ret -= tmp
    #ret *= coms[n]
    ret %= MOD
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(K, S)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===
def fast_pow(num, kata, mod):
    if kata == 0:
        return 1

    res = 1
    while kata > 0:
        if kata & 1 == 1:
            res = res * num % mod
        num = num * num % mod

        kata >>= 1
    return res


def choose(n, r, MOD):
    res = 1
    fac = 1
    for i in range(r):
        res *= n - i
        res %= MOD
        fac *= i + 1
        fac %= MOD
    return res * fast_pow(fac, MOD - 2, MOD) % MOD


# nCrの左項にはn以外も来るバージョン、1!～(n-1)!を保持
def prepare(n, MOD):
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    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 main():
    k = ni()
    s = input()
    l = len(s)

    # 使い方
    facts, invs = prepare(k + l, MOD)

    ans = 0
    for ki in range(k + 1):
        tmpa = fast_pow(25, k - ki, MOD)
        tmpb = fast_pow(26, ki, MOD)
        tmpc = facts[k - ki + l - 1] * invs[l - 1] * invs[k - ki + l - 1 - (l - 1)] % MOD
        tmpd = (tmpa * tmpb * tmpc) % MOD
        ans += tmpd
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class Comb:
    def __init__(self, N):
        F = [1] * (N + 1)
        for i in range(N):
            F[i + 1] = (i + 1) * F[i] % mod

        self.d_inv = {}
        self.d_comb = {}
        self.F = F

    def inv(self, a):
        if a not in self.d_inv:
            self.d_inv[a] = pow(a, mod - 2, mod)
        return self.d_inv[a]

    def comb(self, a, b):
        if (a, b) not in self.d_comb:
            self.d_comb[(a, b)] = (self.F[a] * self.inv(self.F[a - b]) * self.inv(self.F[b])) % mod
            self.d_comb[(a, a - b)] = self.d_comb[(a, b)]
        return self.d_comb[(a, b)] 


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

    F25 = [1] * (K + 2)
    F26 = [1] * (K + 2)
    T = [1] * (K + 2)
    for i in range(K + 1):
        F25[i + 1] = (25 * F25[i]) % mod
        F26[i + 1] = (26 * F26[i]) % mod
        if i != 0:
            T[i] = pow(i, mod - 2, mod)

    r = 1
    res = 0
    for k in range(K + 1):
        res += ((F25[k] * F26[K - k]) % mod * r) % mod
        r *= (len(S) - 1 + k + 1)
        r %= mod
        r *= T[k + 1]
        r %= mod
        res %= mod
     
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    mod=1000000007
    inv=lambda x: pow(x,mod-2,mod)
    k=int(input())
    s=input().strip()
    l=len(s)
    
    n=k+l
    Fact=[1] #階乗
    for i in range(1,n+1):
        Fact.append(Fact[i-1]*i%mod)
    Finv=[0]*(n+1) #階乗の逆元
    Finv[-1]=inv(Fact[-1])
    for i in range(n-1,-1,-1):
        Finv[i]=Finv[i+1]*(i+1)%mod
    def comb(n,r):
        if n<r:
            return 0
        return Fact[n]*Finv[r]*Finv[n-r]%mod

    ans=0
    p=1
    for i in range(l,l+k+1)[::-1]:
        ans+=comb(l+k,i)*p
        ans%=mod
        p*=25
        p%=mod
    print(ans)
    
if __name__=='__main__':
    main()

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=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(3*10**6,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

dp=[[0]*(K+len(S)+1) for _ in range(2)]
for i in range(len(S)-1,K+len(S)+1):
    dp[0][i]=COM(i,i-len(S)+1)*pow(25,i-len(S)+1,MOD)
dp[1][len(S)]
for i in range(K+len(S)):
    dp[1][i+1]=dp[1][i]*26+dp[0][i]
    dp[1][i+1]%=MOD
print(dp[1][-1])

Submission status: Accepted

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

mod=10**9+7
ruijo_5=[1]
ruijo_6=[1]

lim=n+len(s)+10

for i in range(n):
    ruijo_5.append(ruijo_5[i]*25%mod)
    ruijo_6.append(ruijo_6[i]*26%mod)

#print(ruijo_5)
#print(ruijo_6)

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod


factorial = [1]
for i in range(1, lim):
    factorial.append(factorial[i-1]*i%mod)

inverseFactorial = [0] * lim
inverseFactorial[lim-1] = power(factorial[lim-1], mod-2)
for i in range(lim-2, -1, -1):
    inverseFactorial[i] = inverseFactorial[i+1] * (i+1) % mod

def combi(i, j):
    return factorial[i] * inverseFactorial[j] * inverseFactorial[i-j] % mod


#print(len(factorial))
#print(len(inverseFactorial))

kai=len(s)-1
#print(kai)
s=0

for i in range(n+1):
    #print(combi(kai+i,i),ruijo_5[i],ruijo_6[n-i])
    tasu=combi(kai+i,i)*ruijo_5[i]%mod
    tasu*=ruijo_6[n-i]
    tasu%=mod
    s+=tasu
    s%=mod

print(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 #出力の制限
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 = str(input())
l = len(s)
ans = 0
def power(a,n):
  ans = 1
  while n:
    if n%2:
      ans = (ans*a)%mod
    a = (a*a)%mod
    n >>= 1
  return ans%mod  
y = 1
for i in range(l,l+k+1):
  x = power(26,l+k-i)
  ans = (ans+ x*y*cmb(i-1,l-1,mod))%mod
  y = (y*25)%mod
print(ans)

Submission status: Accepted

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

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

mod = 10**9+7
N = K+S

# mod上の逆元の計算
inverse = [0, 1]
for i in range(2, N+1):
    inverse.append((-inverse[mod%i]*(mod//i))%mod)

# 階乗とその逆元の計算
factorial = [1, 1]
factorial_inv = [1, 1]
for i in range(2, N+1):
    factorial.append((factorial[-1]*i)%mod)
    factorial_inv.append((factorial_inv[-1]*inverse[i])%mod)

answer = 0
pow = -1
for i in range(K+1):
    if pow == -1:
        pow = 1
    else:
        pow = (pow*25)%mod
    answer = (answer+pow*factorial[N]*factorial_inv[i]*factorial_inv[N-i])%mod
print(answer)

Submission status: Accepted

Solution code:
mod = 10**9 + 7  # 998244353 # 変える


def table():
    k = 2 * 10**6 + 5  # 変える
    fac = [1] * k
    finv = [1] * k
    inv = [0] * k
    inv[1] = 1
    for i in range(2, k):
        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


fac, finv = table()


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


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

Submission status: Accepted

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

mod = 10**9 + 7

## nCkのmodを求める関数
# テーブルを作る(前処理)
max = 2 * 10**6 + 100
fac, finv, inv = [0]*max, [0]*max, [0]*max

def comInit(max):
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

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

comInit(max)

# 二項係数の計算
def com(n,k):
    if(n < k):
        return 0
    if( (n<0) | (k < 0)):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

ans = 0
ex25 = [1] * (k+1)
ex26 = [1] * (k+1)
for i in range(1,k+1):
    ex25[i] = (ex25[i-1] * 25)%mod
    ex26[i] = (ex26[i-1] * 26)%mod

for i in range(k+1):
    j = k-i
    tmp = pow(25,i,mod) * com(n+i-1,i) * pow(26,j,mod)
    tmp = ex25[i] * com(n+i-1,i) * ex26[j]
    ans = (ans+tmp)%mod

print(ans)

Submission status: Accepted

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

n=k+l
mod=10**9+7
fac = [1, 1]  # fact[n] = (n! mod p)
finv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

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

def comb(n, r, mod):
    if n < r or r < 0:
        return 0
    elif r==0 or r==n:
        return 1
    else:
        return fac[n] * finv[r] * finv[n - r] % mod
print( sum( (comb(k+l,m,mod) * pow(25,m,mod))%mod for m in range(k+1) )%mod )

Submission status: Accepted

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

now = 1
for _ in range(n+l):
  now *= 25
  now %= mod
#print(now)
def inv(x):
  y = 1
  while x != 1:
    y *= mod // x + 1
    x -= mod % x
  return y
ans = 0
#print('#')
for i in range(n+l):
  now *= (n+l-i)
  now *= inv(i+1)
  now *= inv(25)
  now %= mod
  if i+1 >= l:
    ans += now
    ans %= mod
  #print(now)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
# from fractions import gcd

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)


class Combination:
    def __init__(self, mod=10**9+7, n=202020):
        self.f = [0] * n
        self.rf = [0] * n
        self.inv = [0] * n
        self.f[0], self.f[1] = 1, 1
        self.rf[0], self.rf[1] = 1, 1
        self.inv[1] = 1
        self.MOD = mod
        for i in range(2, n):
            self.f[i] = (self.f[i - 1] * i) % self.MOD
            self.inv[i] = (-self.inv[self.MOD % i] * (self.MOD // i)) % self.MOD
            self.rf[i] = (self.rf[i - 1] * self.inv[i]) % self.MOD

    def __call__(self, n, r):
        return (self.f[n] * self.rf[r] * self.rf[n - r]) % self.MOD


C = Combination(mod=MOD, n=2020202)

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

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

print(ans)

Submission status: Accepted

Solution code:
K=int(input())
S=input()
M=len(S)
N=K+M
mod=10**9+7
ans=pow(26,N,mod)
class Data():
    def __init__(self):
        self.power=1
        self.rev=1     
class Combi():
    def __init__(self,N,mod):
        self.lists=[Data() for _ in range(N+1)]
        self.mod=mod  
        for i in range(2,N+1):
            self.lists[i].power=((self.lists[i-1].power)*i)%self.mod
        self.lists[N].rev=pow(self.lists[N].power,self.mod-2,self.mod)
        for j in range(N,0,-1):
            self.lists[j-1].rev=((self.lists[j].rev)*j)%self.mod

    def combi(self,K,R):
        if K<R:
            return 0
        else:
            return ((self.lists[K].power)*(self.lists[K-R].rev)*(self.lists[R].rev))%self.mod
        
c=Combi(2*10**6,mod)
for i in range(M):
    ans-=c.combi(N,i)*pow(25,N-i,mod)
    ans%=mod
print(ans%mod)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

# MOD combination
def cmb(n, r, mod=10**9+7):
    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*2+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 )

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

Submission status: Accepted

Solution code:
K = int(input())
S = input()
N = len(S)
mod = 7 + 10 ** 9
fact = [1] * (N + K + 1)
for i in range(1, N + K + 1): fact[i] = (fact[i-1] * i) % mod
revfact = [1] * (N + K + 1)
revfact[N + K] = pow(fact[N + K], mod - 2, mod)
for i in reversed(range(1, N + K)):
    revfact[i] = ((i + 1) * revfact[i + 1]) % mod

def comb(n, r):
    return (fact[n] * revfact[n-r] * revfact[r]) % mod

def solve():
    ans = 0
    for k in range(K + 1):
        leftMost = pow(26, k, mod) 
        right = (pow(25, K - k, mod) * comb(N + K - k - 1, N - 1)) % mod
        ans += (leftMost * right) % mod
        ans %= mod
    print(ans)


    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque
import math

# import copy
# from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7

def divide(k):
    return pow(k, MOD-2, MOD)


def make_nck(n):
    ret = [1]
    for i in range(1, n+1):
        ret.append((ret[-1] * (n + 1 - i) * divide(i)) % MOD)

    # print(ret)
    return ret

def make_nigojyo(n):
    ret = [1]

    for i in range(1, n+1):
        ret.append((ret[-1] * 25) % MOD)

    # print(ret)
    return ret


def solve():
    K = getN()
    S = getS()
    l = len(S)
    nck = make_nck(K + len(S))
    nigojyo = make_nigojyo(K + l)
    # ans = 1
    # for i in range(K):
    #     ans *= 2 * (l + 1) - l
    #     ans
    #     l += 1
    #     ans %= MOD
    ans = 0

    for i in range(l + K - l + 1):
        ans += (nigojyo[i]) * nck[i]
        ans %= MOD
        # print(ans)

    print(ans)



def main():
    n = getN()
    for _ in range(n):
        solve()


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

Submission status: Accepted

Solution code:
class Combination:
    def __init__(self, n, mod):
        self.mod = mod

        # self.fac[i] ≡ i! (factorial:階乗)
        l = [1]
        num = 1
        for i in range(1, n+1):
            num *= i
            num %= mod
            l.append(num)
        self.fac = l.copy()

        # self.rec[i] ≡ 1 / i! (reciprocal:逆数)
        num = pow(num, mod-2, mod)
        l = [1 for i in range(n+1)]
        l[n] = num
        for i in range(n-1, 0, -1):
            num *= i + 1
            num %= mod
            l[i] = num
        self.rec = l.copy()

    # comb(n, r) ≡ nCr
    def comb(self, n, r):
        return self.fac[n] * self.rec[r] * self.rec[n - r] % self.mod

mod = 10**9 + 7

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

c = Combination(k + n, mod)

ans = 0
for i in range(k+1):
    ans += c.comb(n + i - 1, i) * pow(25, i, 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

factorials = [1]
fact_invs = [1]
for i in range(1, L+K+1):
    factorials.append((factorials[-1]*i) % MOD)
    fact_invs.append(pow(factorials[-1], MOD-2, MOD))

ans = 1
for i in range(K):
    b = L + i
    a = L - 1
    nans = factorials[b]
    nans *= fact_invs[a]
    nans %= MOD
    nans *= fact_invs[b-a]
    nans %= MOD
    nans *= pow(25, b-a, MOD)
    nans %= MOD
    nans += ans * 26
    nans %= MOD
    ans = nans
print(ans)

Submission status: Accepted

Solution code:
k=int(input())
s=len(input())
mod=10**9+7
fact=[1]*(k+s+1)
inv=[1]*(k+s+1)
for i in range(2,k+s+1):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(k+s,1,-1):
    inv[i-1]=inv[i]*i%mod
def comb(x,y):return fact[x]*inv[y]%mod*inv[x-y]%mod if x>=y>=0 else 0
ans=pow(26,k+s,mod)
for i in range(s):
    ans=(ans-pow(25,k+s-i,mod)*comb(k+s,i)%mod)%mod
print(ans)