AtCoder ABC171 F問題 高速化の方法

Question

前提・実現したいこと・発生している問題

AtCoder ABC171について、解説通りにコードを書いたつもりでしたが、30ケース中14例でTLEとなってしまいました。
どのように高速化をすれば良いかを教えていただけますでしょうか。
問題：https://atcoder.jp/contests/abc171/tasks/abc171_f

また、解説では「適切な前処理をすれば」とありました。↓
解説PDF： https://img.atcoder.jp/abc171/editorial.pdf
私は「階乗とコンビネーションを先に処理して持っておく」ことだと考えたのですが、本来は何を指していたのでしょうか。
よろしくお願い致します

該当のソースコード

import math
k = int(input())
s = input()

ss = len(s)

mod = 10**9 + 7

m25 = [] # 25の階乗をmodで割ったあまりを記録する配列
m26 = [] # 26の階乗
mfc = [] # ss+k-i-1 C ss-1 をi=kから記録していく
a = 1
b = 1
c = 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(k):
    mfc.append(c)
    c *= ss + i # 分子の変化
    c = c // (i+1) #分母の変化 割り算が入るためmod計算は後回し
mfc.append(c) # 最後の項なのであとで足しておく

samu = 0
for i in range(k+1):
    sm = mfc[k-i] #かなり大きな数になっていると考えられるので、次で一度mod計算
    sm %= mod
    sm *= m25[k-i]
    sm *= m26[i]
    sm %= mod
    samu += sm

samu %= mod
print(samu)

試したこと

PyPyでの提出でもTLE数は変化しませんでした。
また初めはループ内で毎回コンビネーションを計算していましたが、ほぼ前例TLEとなりました。
以下の解答例を参考に考えましたが、前処理が何をしているのかわかりませんでした。
https://atcoder.jp/contests/abc171/submissions/14562582

Answer 1

コンビネーションの計算を行うときにmodを取らずに計算してるせいで多倍長整数が使われてることが原因でしょう
「階乗　逆元」で調べれば解答例にあるようなやり方を解説してるサイトが見つかるので参考にしてください。

Comments

[shake9]

ありがとうございます！
このような概念があるのですね、全く知らなかったです。
おかげさまでACできました。