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:
#!usr/bin/env pypy3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def LS(): return [list(x) for x in sys.stdin.readline().split()]


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


def LIR(n):
    return [LI() for i in range(n)]


def SR(n):
    return [S() for i in range(n)]


def LSR(n):
    return [LS() for i in range(n)]


sys.setrecursionlimit(1000000)
MOD = 1000000007


class FactInv:
    def __init__(self, N, MOD=1000000007):
        fact = [1]*(N+1)
        for i in range(1, N+1):
            fact[i] = fact[i - 1] * i % MOD

        inv = [None]*(N+1)
        inv[N] = pow(fact[N], MOD - 2, MOD)

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

        self.N = N
        self.MOD = MOD
        self.fact = fact
        self.inv = inv

    def perm(self, a, b):
        if a > self.N or b > self.N:
            raise ValueError(
                "\nPermutaion arguments are bigger than N\n N = {}, a = {}, b = {}".format(self.N, a, b))
        return self.fact[a] * self.inv[a-b] % self.MOD

    def comb(self, a, b):
        if a > self.N or b > self.N:
            raise ValueError(
                "\nCombination arguments are bigger than N\n N = {}, a = {}, b = {}".format(self.N, a, b))
        return self.fact[a] * self.inv[b] * self.inv[a-b] % self.MOD


def main():
    K = I()
    l = len(S())

    fi = FactInv(K + l + 1)

    ans = 0

    for x in range(K+1):
        ans += fi.comb(l + K - x - 1, l - 1) * \
            pow(25, K - x, MOD) * pow(26, x, MOD) % MOD
        ans %= MOD

    print(ans)


main()

Submission status: Accepted

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

N = n + k - 1

mod = 1000000007
fact = [1] * (N + 1)
ifact = [1] * (N + 1)

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


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


m25 = [1]
for i in range(k):
    m25.append(m25[i] * 25 % mod)
m26 = [1]
for i in range(k):
    m26.append(m26[i] * 26 % mod)

ans = 0
for i in range(k + 1):
    p = m25[k - i] * m26[i] % mod
    p *= comb(n + k - i - 1, n - 1)
    p %= mod
    ans += p
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
K=int(input())
S=input()
M=10**9+7
#----------------------------------------------------------------
f=1
Fact=[f]
for i in range(1,len(S)+K+1):
    f=(f*i)%M
    Fact.append(f)

Inv=[0]*(len(S)+K+1)
g=pow(f,M-2,M)
Inv=[0]*(len(S)+K+1)
Inv[-1]=g
for j in range(len(S)+K-1,-1,-1):
    Inv[j]=(Inv[j+1]*(j+1))%M

def nCr(n,r):
    if 0<=r<=n:
        return (Fact[n]*Inv[r]*Inv[n-r])%M
    else:
        return 0

A=len(S)

T=0
for i in range(K+1):
    T=(T+nCr(A+K-1-i,K-i)*pow(25,K-i,M)*pow(26,i,M))%M
print(T)

Submission status: Accepted

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

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

N = 2 * (10 ** 6) + 100
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)

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

Submission status: Accepted

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

mod = 10**9 + 7

class Combination:
    def __init__(self, n):
        self.facts = [1 for i in range(n+1)]
        self.invs = [1 for i in range(n+1)]
        
        for i in range(1, n+1):
            self.facts[i] = self.facts[i-1] * i % mod
            self.invs[i] = pow(self.facts[i], mod-2, mod)

    def ncr(self, n, r):
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0
        else:
            return self.facts[n] * self.invs[r] * self.invs[n-r] % mod

    def nhr(self, n, r):
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0
        else:
            return self.ncr(n+r-1, n-1)

N = K+len(S)
comb = Combination(K+len(S))

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

print(ans)

Submission status: Accepted

Solution code:
#標準入力　テスト
import sys
input = lambda: sys.stdin.readline().rstrip()
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)

Submission status: Accepted

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

framod=[1]
def framod_calc(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
        framod.append(a)
framod_calc(n+k+1, mod)

def combmod(n, k, mod):
    a=framod[n]
    b=framod[k]
    c=framod[n-k]
    return (a * pow(b, mod-2, mod) * pow(c, mod-2, mod)) % mod

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

Submission status: Accepted

Solution code:
import sys
import math
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    MOD = 10 ** 9 + 7

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

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

    N = 10 ** 6 * 2
    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)

    ans = 0
    a = 1
    b = pow(26, K, MOD)
    for i in range(K + 1):
        ans += a * cmb(i + len(S) - 1, len(S) - 1, MOD) * b
        a = a * 25 % MOD
        b = b * pow(26, MOD - 2, MOD) % MOD

    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
K=int(input().rstrip())
S=input().rstrip()
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)

Submission status: Accepted

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

length = len(S)
length_all = K + length
ans = 0
list_25 = [1] * (10**6 + 5)
list_26 = [1] * (10**6 + 5)
for i in range(1,10**6 + 5):
  list_25[i] = list_25[i - 1] * 25 % MOD
  list_26[i] = list_26[i - 1] * 26 % MOD
  
fact = [1] * (2 * 10**6 + 5)
fact_inv = [1] * (2 * 10**6 + 5)
for i in range(1, 2 * 10**6 + 5):
  fact[i] = fact[i-1] * i % MOD
  fact_inv[i] = fact_inv[i - 1] * pow(i, MOD - 2, MOD) % MOD

for i in range(K + 1):
  ans += list_26[i] * list_25[K - i] % MOD * fact[length_all - i - 1] * fact_inv[length - 1] * fact_inv[K - i] % MOD

print(ans % MOD)

Submission status: Accepted

Solution code:
import sys

K = int(sys.stdin.readline())
M = len(sys.stdin.readline())-1
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


X = Combi(N, mod)
for i in range(M):
    ans -= X.combi(N, i)*pow(25, N-i, mod)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    MOD = 10 ** 9 + 7

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

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

    N = 10 ** 6 * 2
    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)

    ans = 0
    for i in range(K + 1):
        if len(S) == 1:
            ans += pow(25, i, MOD) * pow(26, K - i, MOD)
        else:
            ans += pow(25, i, MOD) * cmb(i + len(S) - 1, len(S) - 1, MOD) * pow(26, K - i, MOD)

    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
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+10000,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:
from pprint import pprint
import sys

K = int(sys.stdin.readline())
S = sys.stdin.readline().strip()

ls = len(S)


mod = 10**9 + 7
MAX = ls + K + 100
factorial = [1] * (MAX+1)
t = 1
for i in range(1, MAX+1):
    t = (t * i) % mod
    factorial[i] = t
def combination(n, x, mod=10**9+7):
    # nCx
    # 組み合わせ
    # ex) combination(5, 2) = 10
    # factorial = [1] * (n+1)
    # t = 1
    # for i in range(1, n+1):
    #     t = (t * i) % mod
    #     factorial[i] = t
    tmp = factorial[n]
    tmp = (tmp * pow(factorial[x], mod-2, mod)) % mod
    tmp = (tmp * pow(factorial[n-x], mod-2, mod)) % mod
    return tmp



# Sの部分文字列を埋め込む場所のパターン
# S + K choose S

# Snを配置する場所ごとに全パターンを計算
ans = 0
for i in range(ls-1, ls + K):	
    tmp = pow(25, i-ls+1, mod) 
    tmp *= pow(26, ls + K - i - 1, mod) 
    comb = combination(i, ls-1)
    tmp *= comb
    tmp %= mod
    ans += tmp
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

class ModTools:
    """ 階乗・逆元用のテーブルを構築する """

    def __init__(self, MAX, MOD):

        # nCrならn、nHrならn+rまで作る
        MAX += 1
        self.MAX = MAX
        self.MOD = MOD
        factorial = [1] * MAX
        factorial[0] = factorial[1] = 1
        for i in range(2, MAX):
            factorial[i] = factorial[i-1] * i % MOD
        inverse = [1] * MAX
        inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
        for i in range(MAX-2, -1, -1):
            inverse[i] = inverse[i+1] * (i+1) % MOD
        self.fact = factorial
        self.inv = inverse

    def nCr(self, n, r):
        """ 組み合わせ """

        if n < r: return 0
        r = min(r, n-r)
        numerator = self.fact[n]
        denominator = self.inv[r] * self.inv[n-r] % self.MOD
        return numerator * denominator % self.MOD

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

mt = ModTools(2*10**6, MOD)
ans = 0
for x in range(0, K+1):
    ans += mt.nCr(N+K-x-1, N-1) * pow(25, K-x, MOD) * pow(26, x, MOD) % MOD
ans %= MOD
print(ans)

Submission status: Accepted

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

class Facts():
   # O(max_num)
   def __init__(self, max_num=10**5, p=10**9+7):
      self.p = p
      self.max_num = max_num
      self.fact = [1] * (self.max_num + 1)
      self.rev = [1] * (self.max_num + 1)
      for i in range(1, self.max_num + 1):
         self.fact[i] = (self.fact[i-1] * i) % self.p
      self.rev[self.max_num] = self.mod_pow(self.fact[self.max_num], self.p-2)
      for i in range(self.max_num-1, 0, -1):
         self.rev[i] = self.rev[i+1] * (i + 1) % self.p

   def comb(self, n, k):
      if n < 0 or k < 0 or n < k:
         return 0
      if n == 0 or k == 0:
         return 1
      res = ((self.fact[n] * self.rev[k] % self.p) * self.rev[n - k]) % self.p
      return res

   def comb_base(self, n, k):
      if n < 0 or k < 0 or n < k:
         return 0
      if n == 0 or k == 0:
         return 1
      a, b = 1, 1
      for i in range(k):
         a *= (n-i)
         a %= MOD
      for i in range(k):
         b *= (k-i)
         b %= MOD
      return (a*self.mod_pow(b, self.p-2)) % self.p

   def perm(self, n, k):
      if n < 0 or k < 0 or n < k:
         return 0
      if n == 0 or k == 0:
         return 1
      a = self.fact[n]
      b = self.fact[n-k]
      return (a * self.mod_pow(b, self.p-2)) % self.p

   def mod_pow(self, a, b):
      ans = 1
      while b > 0:
         if b & 1:
            ans = ans * a % self.p
         a = a * a % self.p; b >>= 1
      return ans

r26 = [1 for _ in range(k + 1)]
r25 = [1 for _ in range(k + 1)]
for i in range(1, k+1):
   r26[i] = (r26[i-1] * 26) % MOD
   r25[i] = (r25[i-1] * 25) % MOD
facts = Facts(max_num=len(s)+k+1, p=MOD)

total = len(s) + k
ans = 0
for s_n in range(len(s), total+1):
   d = total - s_n
   ans += facts.comb(total - d - 1, len(s) - 1) * r25[k-d] * r26[d]
   ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7
class mint:
    def __init__(self, x):
        self.x = x % MOD if isinstance(x, int) else int(x) % MOD
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x += MOD-other.x if isinstance(other, mint) else MOD-other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __imod__(self, other):
        self.x %= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __mod__(self, other):
        return (
            mint(self.x % other.x) if isinstance(other, mint) else
            mint(self.x % other)
        )
    def __truediv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rmod__(self, other):
        return (
            mint(other.x % self.x) if isinstance(other, mint) else
            mint(other % self.x)
        )
    def __rtruediv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )
class Comb():
    # class <mint> should be imported
    def __init__(self, n):
        self.n = n
        fact = [0]*(n+1) # 1-indexed
        ifact = [0]*(n+1) # 逆元
        fact[0] = mint(1)
        for i in range(1, n+1):
            fact[i] = fact[i-1]*i
        ifact[-1] = pow(fact[-1], MOD-2)
        for i in range(n, 0, -1):
            ifact[i-1] = ifact[i]*i
        self.fact = fact
        self.ifact = ifact
    def calc(self, n, k):
        if k<0 or k>n:
            return 0
        return self.fact[n]*self.ifact[k]*self.ifact[n-k]
cb= Comb(2000005)

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

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

print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
M = 2 * 10 ** 6
fac = [1] * (M + 1)
for i in range(len(fac) - 1):
    fac[i + 1] = fac[i] * (i + 1) % MOD


def comb(n, k):
    return fac[n] * pow(fac[n - k], MOD - 2, MOD) * pow(fac[k], MOD - 2, MOD) % MOD


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

Submission status: Accepted

Solution code:
MOD = 10**9+7

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

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


ifactorial = [0] * (MAX + 1)
ifactorial[MAX] = pow(factorial[MAX], MOD - 2, MOD)
for i in range(MAX, 0, -1):
    ifactorial[i - 1] = ifactorial[i] * i % MOD

pow25 = [1] * (k + 1)
pow26 = [1] * (k + 1)
for i in range(k):
    pow25[i + 1] = pow25[i] * 25
    pow25[i + 1] %= MOD
    pow26[i + 1] = pow26[i] * 26
    pow26[i + 1] %= MOD


def combination(n, k):
    ret = factorial[n] * ifactorial[k] * ifactorial[n - k]
    return ret % MOD


ans = 0
for i in range(k + 1):
    tmp = combination(i + len(s) - 1, len(s) - 1)
    tmp *= pow25[i]
    tmp %= MOD
    # tmp *= pow(25, i, MOD)
    tmp *= pow26[k - i]
    # tmp *= pow(26, k - i, MOD)
    tmp %= MOD
    ans += tmp
    ans %= MOD
print(ans)

Submission status: Accepted

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


N = len(S)
M = K+N
s = [pow(26,K,MOD)]

r26 = pow(26,MOD-2,MOD)
for i in range(1,K+1):
    t = s[-1]
    t *= r26
    t *= 25
    t *= N+i-1
    t *= pow(i,MOD-2,MOD)
    t %= MOD
    s.append(t)


ans = sum(s) % MOD
print(ans)

Submission status: Accepted

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

class Facts():
   # O(max_num)
   def __init__(self, max_num=10**5, p=10**9+7):
      self.p = p
      self.max_num = max_num
      self.fact = [1] * (self.max_num + 1)
      self.rev = [1] * (self.max_num + 1)
      for i in range(1, self.max_num + 1):
         self.fact[i] = (self.fact[i-1] * i) % self.p
      self.rev[self.max_num] = self.power_func(self.fact[self.max_num], self.p-2)
      for i in range(self.max_num-1, 0, -1):
         self.rev[i] = self.rev[i+1] * (i + 1) % self.p

   def comb(self, n, k):
      if n < 0 or k < 0 or n < k:
         return 0
      if n == 0 or k == 0:
         return 1
      res = ((self.fact[n] * self.rev[k] % self.p) * 
               self.rev[n - k]) % self.p
      return res

   def power_func(self, a, b):
      # a^b mod p
      # O(log(b))
      ans = 1
      while b > 0:
         if b & 1:
               ans = ans * a % self.p
         a = a * a % self.p
         b >>= 1
      return ans

r26 = [1 for _ in range(k + 1)]
r25 = [1 for _ in range(k + 1)]
for i in range(1, k+1):
   r26[i] = (r26[i-1] * 26) % MOD
   r25[i] = (r25[i-1] * 25) % MOD
facts = Facts(max_num=len(s)+k+1, p=MOD)

total = len(s) + k
ans = 0
for s_n in range(len(s), total+1):
   d = total - s_n
   ans += facts.comb(total - d - 1, len(s) - 1) * r25[k-d] * r26[d]
   ans %= MOD

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)

Submission status: Accepted

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

len_S=len(S)

#逆元を用いたコンビネーション
mod = 10**9+7
def mul_mod(a,b):
  return (a*b) % mod

def fact_inv(a):
  ans = 1
  for i in range(1,a+1):
    ans = (pow(i,mod-2,mod) * ans) % mod
  return ans

fact_list = [1]
for i in range(1,len_S+K):
  fact_list.append(mul_mod(fact_list[-1],i))

fact_list_inv = [1]
for i in range(1,len_S+K):
  fact_list_inv .append((pow(i,mod-2,mod) * fact_list_inv[-1]) % mod)
def comb_inv_mod(a,b):
  tmp = (fact_list[a]*fact_list_inv[b]) % mod
  return (tmp*fact_list_inv[a-b]) % mod

ans = 0
for i in range(len_S-1,len_S+K): #Snの位置
  #print(i)
  #ans += comb_inv(len_S+K-(len_S+K-i-1)-1,N-1)*pow(25,(K-(len_S+K-i-1)),mod)*pow(26,len_S+K-i-1,mod)
  A = comb_inv_mod(i,len_S-1)*pow(25,i-len_S+1,mod) % mod 
  A = A*pow(26,len_S+K-i-1,mod) % mod
  ans += A
  #print(ans)
  ans = ans % mod
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

lim = 2*(10**6)  # 必要そうな階乗の限界を入れる
fact = [1] * (lim+1)
fact_inv = [1] * (lim+1)
for n in range(1, lim+1):
    fact[n] = (fact[n-1] * n) % mod
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
    fact_inv[n-1] = (n * fact_inv[n]) % mod
def C(n, r):
    return (((fact[n] * fact_inv[r]) % mod) * fact_inv[n-r]) % mod

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

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

Submission status: Accepted

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

class Facts():
    # O(max_num)
    def __init__(self, max_num=10**5, p=10**9 + 7):
        self.p = p
        self.max_num = max_num
        self.fact = [1] * (self.max_num + 1)
        for i in range(1, self.max_num + 1):
            self.fact[i] = self.fact[i-1] * i
            self.fact[i] %= self.p

    def comb(self, n, k):
        # nCk mod p with memo
        # O(log(p))
        if n < 0 or k < 0 or n < k:
            return 0
        if n == 0 or k == 0:
            return 1
        a = self.fact[n]
        b = self.fact[k]
        c = self.fact[n-k]
        return (a*self.power_func(b, self.p-2) *
                self.power_func(c, self.p-2)) % self.p

    def power_func(self, a, b):
        # a^b mod p
        # O(log(b))
        ans = 1
        while b > 0:
            if b & 1:
                ans = ans * a % self.p
            a = a * a % self.p
            b >>= 1
        return ans

r26 = [1 for _ in range(k + 1)]
r25 = [1 for _ in range(k + 1)]
for i in range(1, k+1):
   r26[i] = (r26[i-1] * 26) % MOD
   r25[i] = (r25[i-1] * 25) % MOD
facts = Facts(max_num=len(s)+k+1, p=MOD)

total = len(s) + k
ans = 0
for s_n in range(len(s), total+1):
   d = total - s_n
   ans += facts.comb(total - d - 1, len(s) - 1) * r25[k-d] * r26[d]
   ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
from sys import stdin
input = stdin.readline
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def modinv2(x,r):
  return pow(x,r-2,r)

def comb(n,a,R):
    return (fact[n]*modinv2(fact[n-a]*fact[a],R))

def factinit(n,R):
    global fact
    fact = [1]*(n+1)
    for i in range(2,n+1):
        fact[i] = (fact[i-1]*i)%R

k = inn()
s = ins()
n = len(s)
factinit(n+k,R)
sm = 0
for m in range(n,n+k+1):
    x = comb(m-1,n-1,R)
    y = pow(25,m-n,R)
    z = pow(26,n+k-m,R)
    sm = (sm+x*y*z)%R
    #ddprint(f"{x=} {y=} {z=} {sm=}")
print(sm)

Submission status: Accepted

Solution code:
K = int(input())
S = input()
M = K + len(S)
alpha = "abcdefghijklmnopqrstuvwxyz"
mod = int(1e9) + 7 # <-- input modulo
maxf = 2000010           # <-- input factional limitation

def doubling(n, m, modulo=mod):
    y = 1
    base = n
    tmp = m
    while tmp != 0:
        if tmp % 2 == 1:
            y *= base
            if modulo > 0:
                y %= modulo
        base *= base
        if modulo > 0:
            base %= modulo
        tmp //= 2
    return y

def inved(a, modulo=mod):
    x, y, u, v, k, l = 1, 0, 0, 1, a, modulo
    while l != 0:
        x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
        k, l = l, k % l
    return x % modulo

fact = [1 for _ in range(maxf+1)]
invf = [1 for _ in range(maxf+1)]

for i in range(maxf):
    fact[i+1] = (fact[i] * (i+1)) % mod
invf[-1] = inved(fact[-1])
for i in range(maxf, 0, -1):
    invf[i-1] = (invf[i] * i) % mod
  
SS = 0
bas = 1
for i in range(M, len(S)-1, -1):
  SS += (bas * invf[i] * invf[M-i]) % mod
  bas *= 25
  bas %= mod
  SS %= mod
print(SS*fact[M]%mod)