\(N\leq 10^{18}\), \(M\leq 10^7\), \(K\leq 10^6\) でも使える解法を解説します。

形式的べき級数 \(f_m\) を \(f_m(x) = \sum_{n}S(n,m)x^n\) により定めると，

• \(f_0(x) = \sum_{n} n^Kx^n\)
• \(f_{i+1}(x) = \frac{f_i(x)}{1-x}\)

が成り立ちます．

\(f_0(x)\) は係数が \(n\) の \(K\) 次多項式であることから \(\frac{A_K(x)}{(1-x)^{K+1}}\) （\(A_K\) は多項式）の形の表示を持ちます．\(A_K\) は \(f_0\) と \((1-x)^{K+1}\) の畳み込みによって \(O(K\log K)\) 時間で計算できます． なお，\(A_K\) は Euler 多項式と呼ばれます．https://oeis.org/A008292

本問は次に帰着されることが分かります．

\(K\) 次多項式 \(F\) が与えられる．\([x^N]\frac{F(x)}{(1-x)^{M+K}}\) を求めよ．

\(F(x) = \sum a_ix^i\) とすれば求めるものは \(\sum_{i}[x^{N-i}]a_i\cdot \frac{1}{(1-x)^{M+K}}\) で，\([x^{N-i}]\frac{1}{(1-x)^{M+K}}\) はよく知られているように適当な二項係数として書くことができます．問題は二項係数いくつかの計算に帰着できて，適切な方法でこれを計算することでこの部分を \(O(M+K)\) 時間で行うことが可能です．

以上により，本問題は全体として \(O(K\log K + M)\) 時間で解くことができます．