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 os
import heapq
import sys
import math
import operator
from collections import defaultdict
from io import BytesIO, IOBase

"""def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)"""


# def pw(a,b):
#     result=1
#     while(b>0):
#         if(b%2==1): result*=a
#         a*=a
#         b//=2
#     return result



def inpt():
    return [int(k) for k in input().split()]


def main():
    k = int(input())
    s = input()
    n = len(s)
    ans = 0
    md = 10 ** 9 + 7
    ar26=[1]
    ar25=[1]
    a=1
    b=1
    nn=1
    rr=1
    num=[1]
    rum=[1]
    for i in range(1,n+k+1):
        nn*=i
        nn%=md
        rr*=i
        rr%=md
        num.append(nn)
        rum.append(rr)

    for i in range(k):
        a*=25
        a%=md
        b*=26
        b%=md
        ar26.append(b)
        ar25.append(a)

    for i in range(k+1):
        ans+=(num[n+k-i-1]*pow((rum[n-1]*rum[k-i])%md,md-2,md)*ar26[i]*ar25[k-i])
        ans%=md
    print(ans)

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

def input():
    return sys.stdin.readline().strip()


def main():
    def make_factorial_table(n):
        result = [0] * (n+1)
        result[0] = 1
        for i in range(1,n+1):
            result[i] = result[i-1] * i % mod
        return result
    
    def nCr(n,r):
        return fact[n] * pow(fact[n-r],mod-2,mod) * pow(fact[r],mod-2,mod) % mod

    K = int(input())
    S = input()
 
    mod = 10 ** 9 + 7
    n = len(S)
    ans = 0
    fact = make_factorial_table(n+K+1)

    for i in range(K+1):
        tmp = pow(25,i,mod)
        tmp *= nCr(i+n-1,n-1)
        tmp *= pow(26,K-i,mod)
        ans += tmp
        ans %= mod
    print(ans)
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
K = int(input())
S = input()
N = len(S)
mod = int(1e9+7)


wk = pow(26,K,mod)
inv26 = pow(26,-1,mod)

ans = wk
for i in range(1,K+1):
  wk = (wk * 25 * inv26) % mod
  wk = (wk * (N-1+i) * pow(i,-1,mod) % mod)
  ans = (ans + wk)%mod
    
print(ans)

Submission status: Accepted

Solution code:
K = int(input())
S = input()
N = len(S)
mod = int(1e9+7)

### 123
### a1bb2ccc3dddd 10文字インサート
# pow(25,6) * pow(26,4) * 8C2
# (3はfixで、それより前の8mojiから1/2を入れる場所を決める）
# これを3の位置でループする（1-indexで 3<=i<=N)

# 123dddddddddd
# pow(25,0) * pow(26,10) * 2C2(1)
# 12x3ddddddddd
# pow(25,1) * pow(26,9) * 3C2( = 2C2 * 3 / 1)
# 12xx3dddddddd
# pow(25,2) * pow(26,8) * 4C2( = 3C2 * 4 / 2)
# ...
# 12xxxxxxxxxx3
# pow(25,10) * pow(26,0) * 12C2( = 11C2 * 12 / 10)

# 5C5, 6C5, 7C5 1, 6, 21, 56
def powinv(x,mod):
  return pow1(x,mod-2,mod)
  
def pow1(x, n, mod):
  ans = 1
  while n>0:
    if n % 2:
      ans *= x
      ans %= mod
    x *= x
    x %= mod
    n = n // 2 # n >>= 1
  return ans

wk = pow(26,K,mod)
inv26 = powinv(26,mod)

ans = wk
for i in range(1,K+1):
  wk = (wk * 25 * inv26) % mod
  wk = (wk * (N-1+i) * powinv(i,mod) % mod)
  ans = (ans + wk)%mod
    
print(ans)

Submission status: Accepted

Solution code:
K = int(input())
S = input()
N = len(S)
mod = int(1e9+7)

### 123
### a1bb2ccc3dddd 10文字インサート
# pow(25,6) * pow(26,4) * 8C2
# (3はfixで、それより前の8mojiから1/2を入れる場所を決める）
# これを3の位置でループする（1-indexで 3<=i<=N)

# 123dddddddddd
# pow(25,0) * pow(26,10) * 2C2(1)
# 12x3ddddddddd
# pow(25,1) * pow(26,9) * 3C2( = 2C2 * 3 / 1)
# 12xx3dddddddd
# pow(25,2) * pow(26,8) * 4C2( = 3C2 * 4 / 2)
# ...
# 12xxxxxxxxxx3
# pow(25,10) * pow(26,0) * 12C2( = 11C2 * 12 / 10)

# 5C5, 6C5, 7C5 1, 6, 21, 56

wk = pow(26,K,mod)
inv26 = pow(26,-1,mod)

ans = wk
for i in range(1,K+1):
  wk = (wk * 25 * inv26) % mod
  wk = (wk * (N-1+i) * pow(i,-1,mod) % mod)
  ans = (ans + wk)%mod
    
print(ans)

Submission status: Accepted

Solution code:
K = int(input())
s = input()
n=len(s)
def find_power(n,mod=10**9+7):
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist
def find_inv_power(n,mod=10**9+7):
    powlist=find_power(n)
    check=powlist[-1]
    first=1
    uselist=[0]*(n+1)
    secondlist=[0]*30
    secondlist[0]=check
    secondlist[1]=check**2
    for i in range(28):
        secondlist[i+2]=(secondlist[i+1]**2)%(10**9+7)
    a=format(10**9+5,"b")
    for j in range(30):
        if a[29-j]=="1":
            first=(first*secondlist[j])%(10**9+7)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7)
    return uselist
mod = 10**9+7
NUM = (2*10**6)+100
p_lis=find_power(NUM,mod)
ip_lis=find_inv_power(NUM,mod)
def comb(n,r,mod=10**9+7):
    if n<r:
        return 0
    elif n>=r:
        return (p_lis[n]*ip_lis[r]*ip_lis[n-r])%(mod)
ans=0
for k in range(K+1):
    ans+=(comb(n-1+K-k,n-1)* pow(25,K-k,mod)* pow(26,k,mod))
print(ans%mod)

Submission status: Accepted

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

MAX = 2*10**6+100
MOD = 10**9+7
fact = [0]*MAX #fact[i]: i!
inv = [0]*MAX #inv[i]: iの逆元
finv = [0]*MAX #finv[i]: i!の逆元
fact[0] = 1
fact[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
    
for i in range(2, MAX):
    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 C(n, r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fact[n]*(finv[r]*finv[n-r]%MOD)%MOD
    
K = int(input())
S = input()[:-1]
L = len(S)
ans = 0

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

print(ans)

Submission status: Accepted

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

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

p = 10 ** 9 + 7
N = 2 * 10**6+3
fact = [1] * ( N + 3)
factinv = [1] * (N + 3)
inv = [0]* (N + 3)
inv[1] = 1

for i in range(2,N+1):
    fact[i] = fact[i-1] * i % p
    inv[i] = p-inv[p % i] * (p//i) % p
    factinv[i] = factinv[i-1] * inv[i] % p

def powmod(a,n,mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n>>=1
    return res

ss = len(S)
ans = 0
k = 1;
for i in range(K+1):
    ans += cmb(ss+K-i-1,ss-1,p) * k * powmod(25,K-i,p)
    ans %= p
    k = k * 26 % p

print(ans)

Submission status: Accepted

Solution code:
import sys
import  math
import fractions
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

mod=10**9+7
K=int(input())
S=list(ns())
N=K+len(S)

class My_pow():
    def __init__(self,n,r,p):
        self.pow=[0]*r
        self.pow[0]=1
        for i in range(1,r):
            self.pow[i]=(self.pow[i-1]*n)%p
    
    def clc_pow(self,r):
        return self.pow[r]

            
class My_comb(): 
    def __init__(self,MOD,Nmax):
        self.p=MOD
        self.fact=[1,1]
        self.factinv=[1,1]
        self.inv=[0,1]
        for i in range(2,Nmax+1):
            self.fact.append((self.fact[-1]*i)%self.p)
            self.inv.append((-self.inv[self.p%i]*(self.p//i))%self.p)
            self.factinv.append((self.factinv[-1]*self.inv[-1])%self.p)


    def comb(self,n,r):
        if(r<0) or (n<r):
            return 0
        r=min(r,n-r)
        return self.fact[n]*self.factinv[r]*self.factinv[n-r]%self.p 


my_comb=My_comb(mod,2*(10**6))
my_pow26=My_pow(26,K+5,mod)
my_pow25=My_pow(25,K+5,mod)

ans=0
for i in range(K+1):
    now =(my_pow26.clc_pow(K-i)*my_pow25.clc_pow(i))
    now *=my_comb.comb(i+len(S)-1,len(S)-1)
    ans += now
    ans%=mod

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

F = 2*10**6+5
mod = 10**9+7
fact = [1]*F
inv = [1]*F
for i in range(2,F):
    fact[i]=(fact[i-1]*i)%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(F-2,1,-1):
    inv[i] = (inv[i+1]*(i+1))%mod

def comb(n,k):
    ans=(fact[n]*inv[n-k])%mod
    return (ans*inv[k])%mod

ans=0

select=pow(25,K,mod)
inv25=inv[25]*fact[24]

for i in range(K+1):
    ans+=select*comb(N-1+K-i,N-1)
    ans%=mod
    select*=inv25*26
    select%=mod

print(ans)

Submission status: Accepted

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

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

modp = mod
max_n = k + len(s)+1 # 必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod modp)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod modp)
inv = [0, 1]  # factinv 計算用

for i in range(2, max_n + 1):
    fact.append((fact[-1] * i) % modp)
    inv.append((-inv[modp % i] * (modp // i)) % modp)
    factinv.append((factinv[-1] * inv[-1]) % modp)

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

Submission status: Accepted

Solution code:
MOD = int(1e9) + 7
MAX = int(2e6) + 7


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


FACT = [1] * (MAX+1)
for i in range(1, MAX+1):
    FACT[i] = (i * FACT[i-1]) % MOD
INV = [1] * (MAX+1)
INV[MAX] = div(1, FACT[MAX])
for i in range(MAX, 0, -1):
    INV[i-1] = (INV[i] * i) % MOD


def combination(m, n):
    return (FACT[m] * INV[n] * INV[m-n]) % MOD


def main():
    K = int(input())
    S = input()
    N = len(S)
    pow25 = [1] * (K+1)
    pow26 = [1] * (K+1)
    for i in range(K):
        pow25[i+1] = (pow25[i] * 25) % MOD
        pow26[i+1] = (pow26[i] * 26) % MOD
    ans = 0
    for m in range(N, N+K+1):
        tmp = (combination(m-1, N-1) * pow25[m-N] * pow26[N+K-m]) % MOD
        ans = (ans + tmp) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#def nCr(n,r):
#    return fact[n]*(inv[n-r]%M)*(inv[r]%M)
M = 1000000007
k = int(input())
s = len(input())
t = k+s
fact = [1]
p25 = [1]
for i in range(1,t+1):
    fact += [(fact[-1] * i)%M]
    if i<=k:
        p25  += [(p25[-1] * 25) % M]

inv = [1]*(t+1)
inv[t] = pow(fact[t], M-2, M)
for i in range(t-1, -1, -1):
    inv[i] = inv[i+1] * (i+1) % M

M = 1000000007
def nCr(n, r, M):
    return fact[n] * inv[n-r] % M * inv[r] % M

n = t#int(input('Enter a number n for checking all its nCr - '))

fact = [1] * (n + 1)
inv = [1] * (n + 1)

for i in range(1, n + 1):
    fact[i] = fact[i-1] * i % M

inv[n] = pow(fact[n], M - 2, M)
for i in range(n-1, -1, -1):
    inv[i] = inv[i + 1] * (i + 1) % M


res = 0
for i in range(k+1):
    #print(nCr(t,t-i))
    res+=nCr(t,t-i,M)*p25[i]
    #print(res)
    res%=M
    #print(res)
print(res)

Submission status: Accepted

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

fct = [1]
invfct = [1]
pow25 = [1]
pow26 = [1]
for i in range(1, K+N+1):
    fct.append(fct[i-1] * i % MOD)
    invfct.append(pow(fct[i], MOD-2, MOD))
    pow25.append(pow25[i-1] * 25 % MOD)
    pow26.append(pow26[i-1] * 26 % MOD)

def cmb(n, k):
    return fct[n] * invfct[k] * invfct[n-k]

ans = 0
for i in range(K+1):
    temp = pow25[i]
    temp *= cmb(i+N-1, N-1)
    temp *= pow26[K-i]
    ans += temp
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
def nCr(n,r):
    return fact[n]*(inv[n-r]%M)*(inv[r]%M)
M = 1000000007
k = int(input())
s = len(input())
t = k+s
fact = [1]
p25 = [1]
for i in range(1,t+1):
    fact += [(fact[-1] * i)%M]
    if i<=k:
        p25  += [(p25[-1] * 25) % M]

inv = [1]*(t+1)
inv[t] = pow(fact[t], M-2, M)
for i in range(t-1, -1, -1):
    inv[i] = inv[i+1] * (i+1) % M


res = 0
for i in range(k+1):
    #print(nCr(t,t-i))
    res+=nCr(t,t-i)*p25[i]
    #print(res)
    res%=M
    #print(res)
print(res)

Submission status: Accepted

Solution code:
M = 10**9 + 7
k,n = int(input()),len(input())
a = t = pow(26,k,M)

for i in range(k):
    t = t*25*(i+n)*pow(26*(i+1),-1,M)%M
    a += t

print(a%M)

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7

def main(K, N, MOD):
    def fact_table(N, MOD):
        inv = np.empty(N, np.int64)
        inv[0] = 0
        inv[1] = 1
        for n in range(2, N):
            q, r = divmod(MOD, n)
            inv[n] = inv[r] * (-q) % MOD
        fact = np.empty(N, np.int64)
        fact[0] = 1
        for n in range(1, N):
            fact[n] = n * fact[n - 1] % MOD
        fact_inv = np.empty(N, np.int64)
        fact_inv[0] = 1
        for n in range(1, N):
            fact_inv[n] = fact_inv[n - 1] * inv[n] % MOD
        return fact, fact_inv, inv

    fact, fact_inv, inv = fact_table(2_000_010, MOD)
    f = np.zeros(K + 1, np.int64)
    f = fact[N - 1:K + N] * fact_inv[N - 1] % MOD * fact_inv[0:K + 1] % MOD

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

if sys.argv[-1] == 'ONLINE_JUDGE':  #　なにそれ
    import numba
    from numba.pycc import CC
    i8 = numba.from_dtype(np.int64)
    signature = (i8, i8, i8)

    cc = CC('my_module')
    cc.export('main', signature)(main)
    cc.compile()


from my_module import main
K = int(readline())
N = len(read().rstrip())

print(main(K, N, MOD))

Submission status: Accepted

Solution code:
class Cmb:
  g1=[1,1]
  g2=[1,1]
  inv=[0,1]
  def __init__(self,mod,upper_limit):
    self.mod=mod
    for i in range(2,upper_limit+1):
      Cmb.g1.append(Cmb.g1[-1]*i%mod)
      Cmb.inv.append(-Cmb.inv[mod%i]*(mod//i)%mod)
      Cmb.g2.append(Cmb.g2[-1]*Cmb.inv[-1]%mod)
  def cmb(self,n,r):
    if r<0 or n<r:
      return 0
    r=min(r,n-r)
    return Cmb.g1[n]*Cmb.g2[r]*Cmb.g2[n-r]%self.mod

k=int(input())
s=len(input())
mod=10**9+7
Cmb=Cmb(mod,k+s)
ans=1
for i in range(1,k+1):
  ans=(ans*26+Cmb.cmb(i+s-1,s-1)*pow(25,i,mod))%mod
print(ans)

Submission status: Accepted

Solution code:
# ライブラリ高速化実験テスト
import sys


class Combi():
    def __init__(self, N, mod):
        self.power = [1 for _ in range(N+1)]
        self.rev = [1 for _ in range(N+1)]
        self.mod = mod
        for i in range(2, N+1):
            self.power[i] = (self.power[i-1]*i) % self.mod
        self.rev[N] = pow(self.power[N], self.mod-2, self.mod)
        for j in range(N, 0, -1):
            self.rev[j-1] = (self.rev[j]*j) % self.mod

    def com(self, K, R):
        if K < R:
            return 0
        else:
            return ((self.power[K])*(self.rev[K-R])*(self.rev[R])) % self.mod

    def pom(self, K, R):
        if K < R:
            return 0
        else:
            return (self.power[K])*(self.rev[K-R]) % self.mod



def input(): return sys.stdin.readline().rstrip()


K = int(input())
S = input()
M = len(S)
N = K+M
mod = 10**9+7
ans = pow(26, N, mod)

c = Combi(2*10**6, mod)
for i in range(M):
    ans -= c.com(N, i)*pow(25, N-i, mod)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
M=10**9+7
k,n=int(input()),len(input())
a=t=pow(26,k,M)
for i in range(k):
  t=t*25*(i+n)*pow(26*-~i,M-2,M)%M
  a+=t
print(a%M)

Submission status: Accepted

Solution code:
M=10**9+7
k,n=int(input()),len(input())
a=t=pow(26,k,M)
for i in range(k):
  t=t*25*(i+n)*pow(26*-~i,-1,M)%M
  a+=t
print(a%M)

Submission status: Accepted

Solution code:
M=10**9+7
k,n=int(input()),len(input())
a=t=pow(26,k,M)
for i in range(1,k+1):
  t=t*25*(i+n-1)*pow(26*i,-1,M)%M
  a+=t
print(a%M)

Submission status: Accepted

Solution code:


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    K=I()
    S=input()
    N=len(S)
    
    def cmb(n, r, mod):
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return (fact[n] * factinv[r] * factinv[n-r])%mod

    fact=[1,1]
    factinv=[1,1]
    inv=[0,1]
    
    for i in range(2, N+K+2 + 1):
        fact.append((fact[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod // i)) % mod)
        factinv.append((factinv[-1] * inv[-1]) % mod)
    
    #Sの条件を初めて満たした時の末端いちで場合分け
    
    #i文字目が末端で，自由枠がj個（iが決まればjも決まるけど，まとめやすいので）
    def calc(i,j):
        temp=pow(26,K-j,mod)#残りの完全自由枠
        temp=(temp*pow(25,j,mod)*cmb(i-1,j,mod))%mod
        return temp
    
    ans=0
    for j in range(K+1):
        i=j+N
        ans=(ans+calc(i,j))%mod
        
    print(ans)


main()

Submission status: Accepted

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

MAX = 2*10**6+100
MOD = 10**9+7
fact = [0]*MAX #fact[i]: i!
inv = [0]*MAX #inv[i]: iの逆元
finv = [0]*MAX #finv[i]: i!の逆元
fact[0] = 1
fact[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
    
for i in range(2, MAX):
    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 C(n, r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fact[n]*(finv[r]*finv[n-r]%MOD)%MOD

K = int(input())
S = input()[:-1]
N = len(S)
ans = 0

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

Submission status: Accepted

Solution code:
import math
k = int(input())
s = len(input())

mod = 10**9 + 7

m25 = [] # 25の階乗をmodで割ったあまりを記録する配列
m26 = [] # 26の階乗
m_n = [1] # 逆元を記録する
a = 1
b = 1

for i in range(k+1):
    m25.append(a)
    a *= 25
    a %= mod

for i in range(k+1):
    m26.append(b)
    b *= 26
    b %= mod

for i in range(2,k+s):
    x = mod % i
    y = mod // i
    c = - m_n[x-1] * y
    c %= mod
    m_n.append(c)

samu = 0
fc = 1
for i in range(k):
    sm = fc
    sm *= m25[i]
    sm *= m26[k-i]
    sm %= mod
    samu += sm

    fc *= (s + i)
    fc %= mod
    fc *= m_n[i]
    fc %= mod

sm = fc
sm *= m25[k]
sm %= mod
samu += sm

samu %= mod
print(samu)

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

class modfact(object):
    def __init__(self, n):
        fact, invfact = [1] * (n + 1), [1] * (n + 1)
        for i in range(1, n + 1): fact[i] = i * fact[i - 1] % MOD
        invfact[n] = pow(fact[n], MOD - 2, MOD)
        for i in range(n - 1, -1, -1): invfact[i] = invfact[i + 1] * (i + 1) % MOD
        self._fact, self._invfact = fact, invfact

    def fact(self, n):
        return self._fact[n]

    def invfact(self, n):
        return self._invfact[n]

    def comb(self, n, k):
        return self._fact[n] * self._invfact[k] % MOD * self._invfact[n - k] % MOD if 0 <= k <= n else 0

    def perm(self, n, k):
        return self._fact[n] * self._invfact[n - k] % MOD if 0 <= k <= n else 0

def resolve():
    k = int(input())
    n = len(input())
    mf = modfact(n + k)
    ans = 0
    for i in range(n, n + k + 1):
        ans += mf.comb(n + k, i) * pow(25, n + k - i, MOD)
        ans %= MOD
    print(ans)
resolve()

Submission status: Accepted

Solution code:
k = int(input())
s = input()
len_s = len(s)
MOD = 1000000007

x_i = pow(26, k, MOD)
r = (25 * pow(26, -1, MOD)) % MOD
comb_i = 1

a = 0
for i in range(k + 1):  
  a += (comb_i  * x_i  ) % MOD
  a %= MOD
  
  x_i  = (x_i  * r) % MOD
  comb_i = (comb_i * (len_s + i) * pow(i + 1, -1, MOD)) % MOD


print(a)

Submission status: Accepted

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

mod = 10**9+7

power25 = [1]*(K+1)
power26 = [1]*(K+1)

def mod_factorial(n, m):
    mod_factorials = [1] * (n + 1)
    for i in range(1, n+1):
        mod_factorials[i] = mod_factorials[i-1]*i
        mod_factorials[i] %= m
    return mod_factorials

# 1!,2!,3!,...,n! の逆元 (mod m)
def mod_inv_factorials2(n, m):
    mod_invs = [1] * (n + 1)
    invs = [1] * (n + 1)
    for i in range(2, n + 1):
        invs[i] = m - invs[m % i] * (m//i) % m

    for i in range(1, n+1):
        mod_invs[i] = invs[i]*mod_invs[i-1]
        mod_invs[i] %= m
    return mod_invs

factrials = mod_factorial(K+N,mod)
inv_factrials = mod_inv_factorials2(max(N,K+1),mod)

for i in range(1,K+1):
    power25[i] = (power25[i-1]*25)%mod
for i in range(1,K+1):
    power26[i] = (power26[i-1]*26)%mod

ans = 0
for i in range(K+1):
    rk = K-i
    ans += power25[rk]*factrials[rk+N-1]*inv_factrials[N-1]*inv_factrials[rk]*power26[i]
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
K = int(input())
S = len(input())
P = 10**9+7
nn = 2*10**6+1
fa = [1] * (nn+1)
fainv = [1] * (nn+1)
for i in range(nn):
    fa[i+1] = fa[i] * (i+1) % P
fainv[-1] = pow(fa[-1], P-2, P)
for i in range(nn)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % P
 
C = lambda a, b: fa[a] * fainv[b] % P * fainv[a-b] % P if 0 <= b <= a else 0

inv = [1]*27
for i in range(2,27):
  inv[i]=(-(P//i)*inv[P%i])%P
ans = 0
a = 1
b = pow(26,K,P)
for i in range(K+1):
  ans = (ans + (C(i+S-1,S-1)*a%P*b%P))%P
  a = a*25%P
  b = b*inv[26]%P
print(ans)

Submission status: Accepted

Solution code:
P = 10**9 + 7

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

d = [0]*(L+K+1)
d[0] = 1
for i in range(1, L+K+1):
    d[i] = (d[i-1]*i)%P

ans = 0
for i in range(K+1):
    temp = pow(26, i, P) * pow(25, K-i, P)
    temp %= P
    temp *= d[L-1+K-i]
    temp %= P
    temp *= pow(d[L-1], P-2, P)
    temp %= P
    temp *= pow(d[K-i], P-2, P)
    temp %= P
    ans += temp
    ans %= P

print(ans)

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    # comb init
    # mod = 1000000007
    nmax = 2 * 10 ** 6 + 10  # change here
    fac = [0] * nmax
    finv = [0] * nmax
    inv = [0] * nmax
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    for i in range(2, nmax):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod

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

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

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



if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1
for i in range(2, MAX + 1):
    fac[i] = fac[i - 1] * i % MOD
    
# Inverse factorial
finv = [0] * (MAX + 1)
finv[MAX] = pow(fac[MAX], MOD - 2, MOD)
for i in reversed(range(1, MAX + 1)):
    finv[i - 1] = finv[i] * i % MOD

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

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

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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


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

l = k+n + 3
 
a25 = [1]
for i in range(l):
    a25.append((a25[-1] * 25) % MOD)
a26 = [1]
for i in range(l):
    a26.append((a26[-1] * 26) % MOD)

fact, inv = prepare(n+k, MOD)
for i in range(k+1):
    c25 = a25[i]
    f = fact[i+n-1] * inv[i] % MOD * inv[n-1] % MOD
    c25 *= f
    c25 %= MOD

    c26 = a26[k-i]
    ans += (c25 * c26 % MOD)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
k = int(input())
s = input()
n = len(s)
mod = 10**9+7
def cmb(n,r,mod):
    r = min(r, n-r)
    return (fact[n] * factinv[r] * factinv[n-r]) % mod
def makefact(n,mod):
    fact = [1,1]
    factinv = [1,1]
    inv = [0,1]
    for i in range(2,n+1):
        fact.append((fact[-1]*i) % mod)
        inv.append(-inv[mod%i]*(mod//i)%mod)
        factinv.append((factinv[-1]*inv[-1])%mod)
    return fact,factinv
fact,factinv = makefact(2*10**6+5,mod)
ans = 0
for i in range(k+1):
    temp = pow(26,i,mod)
    c = cmb(n+k-i-1,n-1,mod)
    temp *= c*pow(25,k-i,mod)
    ans = (ans+temp)%mod
print(ans)

Submission status: Accepted

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

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

frac = [1]*(n+1)
finv = [1]*(n+1)
for i in range(n):
    frac[i+1] = (i+1)*frac[i]%mod
finv[-1] = pow(frac[-1],mod-2,mod)
for i in range(1,n+1):
    finv[n-i] = finv[n-i+1]*(n-i+1)%mod
def nCr(n,r,m):
    if n<0 or r<0 or n<r: return 0
    r = min(r,n-r)
    return frac[n]*finv[n-r]*finv[r]%mod
a,b = [1],[1]
for _ in range(k+1):
    a.append(a[-1]*25%mod)
    b.append(b[-1]*26%mod)
n = len(s)
ans = 0
for i in range(k+1):
    ans += a[i]*b[k-i]*nCr(i+n-1,n-1,mod)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
def calc_inv(n, mod_n):
    inv_li = [0] * (n + 2)
    inv_li[0] = 0
    inv_li[1] = 1
    for i in range(2, n + 2):
        q, r = divmod(mod_n, i)
        inv_li[i] = -inv_li[r] * q % mod_n
    return inv_li


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

MOD = 10**9 + 7
inv = calc_inv(max(K, 26) + 10, MOD)

ans = 0
p = pow(26, K, MOD)

for i in range(1, K + 2):
    ans = (ans + p % MOD) % MOD
    p = p * (s_len + i - 1) * inv[i] * 25 * inv[26] % MOD

print(ans)

Submission status: Accepted

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

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, len(s)+k+5):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

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

Submission status: Accepted

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

mod = 1000000007
decided_keta = len(s)
all_keta = len(s) + k

kai_list = [1 for i in range(2000010)]
for i in range(2,len(kai_list)):
    kai_list[i] = (kai_list[i-1]*i)%mod

answer = 0
for last_given_character_posi in range(decided_keta-1,all_keta):
    given_posi_pattern = kai_list[last_given_character_posi]*pow(kai_list[decided_keta-1],mod-2,mod)%mod*pow(kai_list[last_given_character_posi-decided_keta+1],mod-2,mod)%mod
    char_pattern = pow(25,last_given_character_posi-(decided_keta-1),mod)
    rest_char_pattern = pow(26,all_keta-(last_given_character_posi+1),mod)
    answer = (answer + given_posi_pattern*char_pattern%mod*rest_char_pattern%mod)%mod
print(answer)

Submission status: Accepted

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

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

inv = [0] * (MAX+1)
inv[1] = 1
for i in range(2, MAX+1):
    q, r = divmod(MOD, i)
    inv[i] = -inv[r] * q % MOD

ans = val = pow(26, k, MOD)
for i in range(1, k+1):
    val *= (i+n-1) * 25 * inv[i] * inv[26] % MOD
    val %= MOD
    ans += val
    ans %= MOD
print(ans)

Submission status: Accepted

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

MOD = 10**9+7
d = pow(26, -1, MOD)
ans = val = pow(26, k, MOD)
for i in range(1, k+1):
    val *= (i+n-1) * 25 * pow(i, -1, MOD) * d % MOD
    val %= MOD
    ans += val
    ans %= MOD
print(ans)

Submission status: Accepted

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

fac = [0] * (MAX)
finv = [0] * (MAX)
inv = [0] * (MAX)

def comb_init():
    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
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD


if __name__ == '__main__':
    k = int(input())
    s = input()
    n = len(s)
    comb_init()
    ans = 0
    for i in range(k+1):
        val = comb(i+n-1, n-1)
        val *= pow(25, i, MOD)
        val %= MOD
        val *= pow(26, k-i, MOD)
        val %= MOD
        ans += val
        ans %= MOD
    print(ans)