We are given $n,k$ and $n$ can be very large ($10^9-10^{14}$) but k is relatively small ($k<=2000$).
I tried using sum and product of reciprocal of roots but it fails at the first step itself due to finding the sum of an h.p.
I came up with a recursive form :
$$\operatorname{ans}[n][k]=n\cdot \operatorname{ans}[n-1][k]+\operatorname{ans}[n-1][k-1]$$
which again isn't helpful at all.
Define $f(n, k)$ to be $\prod\limits_{i = 1}^n (x + i)$ truncated to the $x^k$ power. For $n = 0$, we have $f(n, k) = 1$. For $n$ positive and even, we have $$f(n, k)(x) = f(n / 2, k)(x) \times f(n / 2, k)(x + n/2)$$ truncated to the $x^k$ power. The trick is in computing $$f(n / 2, k)(x + n/2)$$ from $f(n/2, k)(x)$. This can be done in $O(k^2)$ time. For $n$ odd, $$f(n, k)(x)= f(n - 1, k)(x) \times(x + n)$$ truncated. The algorithm given by these observations will run in $O(k^2 \log n)$ time.
