Sum of Binomials

解説

$DP_{n,i}$ を、$N=n,R=i$ のときの答えとします（$M$ は与えられたものを使います）。

これは、以下のように計算できます。

• $DP_{1}:$ $(1,0,\dots,0)$ です。
• $DP_{2n,k}:$ $\displaystyle \sum_{(i+j)\bmod M=k} DP_{n,i}DP_{n,j}$ です。$DP_n$ がわかっているとき、$DP_{2n}$ を $O(M^2)$ の時間計算量で計算できます。
• $DP_{n+1,k}:$ $DP_{n,k}+DP_{n,(k-1)\bmod M}$ です。$DP_n$ がわかっているとき、$DP_{n+1}$ を $O(M)$ の時間計算量で計算できます。

繰り返し二乗法と同じ要領で、$O(M^2\log N)$ の時間計算量で $DP_N$ を計算できます。

なお、$DP_{2n,k}$ を高速な畳み込みを用いて計算することで $O(M\log M\log N)$ の時間計算量で答えを求めることもできます。