# 問題

https://yukicoder.me/problems/no/2396

$\left(\sum_{n\geq 0}\binom{N}{Ln+K}M^n\right)\bmod{B}$ を求めよ．

- $1\leq N,M\leq 10^{18}$
- $0\leq K\lt L\leq 10^3$
- $1\leq B\leq 10^9$

# 解法

$B\geq 2$ で解ければよい．

\\[\binom{N}{Ln+K}=[x^N]\frac{x^{Ln+K}}{(1-x)^{Ln+K+1}}\\]

より

\\[\begin{align*}
\sum_{n\geq 0}\binom{N}{Ln+K}M^n
&=[x^N]\sum_{n\geq 0}\frac{x^{Ln+K}}{(1-x)^{Ln+K+1}}M^n\\
&=[x^N]\frac{x^K}{(1-x)^{K+1}}\sum_{n\geq 0}\left(M\frac{x^L}{(1-x)^L}\right)^n\\
&=[x^N]\frac{x^K(1-x)^{L-(K+1)}}{(1-x)^L-Mx^L}\\
\end{align*}\\]

となる．任意MOD畳み込み+Bostan-Moriで $O(L\log L\log N)$．

[実装例](https://yukicoder.me/submissions/896645)