Have you ever felt the need to compute:
$$\sum_{i=0}^N \binom{N}{i} i^K $$
where $N \le 10^9$ and $K \le 10^5$? Well you are in luck, because I’m about to show you how.
Consider the binomial expansion:
$$f_0(x) := (1 + x)^N = \sum_{i=0}^N \binom{N}{i} x^i$$
If you differentiate then multiply by $x$, you will get:
$$f_1(x) := x \frac{\mathrm{d}}{\mathrm{d}x}(1 + x)^N = \sum_{i=0}^N \binom{N}{i}\cdot i \cdot x^i$$
Then repeatedly differentiate and multiply by $x$ (i.e. $f_k(x) = x \frac{\mathrm{d}}{\mathrm{d}x} f_{k - 1}(x)$), then you will end up with:
$$f_K(x) = \sum_{i=0}^N \binom{N}{i} i^K x^i$$
Evaluate $f_K(1)$ then you will get the answer to the original question.
The value of $f_K$ is actually:
$$f_K(x) = \sum_{i=0}^K S(K, i) \cdot (N)_i \cdot (1 + x)^{N-i}$$
where $S$ is the Stirling number of the second kind and $(N)_i$ is the falling factorial $N(N - 1) \ldots (N - i + 1)$. The formula can be easily shown using induction following the property $S(N, K) = K \cdot S(N - 1, K) + S(N - 1, K - 1)$.
The computation of $(N)_i$ for all $0 \le i \le K$ can be easily computed in $O(K)$, and the computation of $S(K, i)$ can be done using FFT (Touchard Polynomial) in $O(K \log K)$.
In case you need something more general:
$$\sum_{i=0}^N \binom{N}{i} \cdot i^K \cdot A^i \cdot B^{N - i} = \sum_{i=0}^K S(K, i) \cdot (N)_i \cdot A^i \cdot (A + B)^{N - i}$$
which can actually be obtained by starting the initial equation from $(Ax + B)^N$.
You can now solve Codeforces edu round problem Cards for $K \le 10^5$.
Another way (and perhaps more elegant way) to arrive at that equation is to use the moment generating function. Let
$$M_X(t) = \mathrm{E}(\exp(tX)) = \sum_{i=0}^\infty \frac{t^i \mathrm{E}(X^i)}{i!}$$
Now, if you differentiate $M_X(t)$ for $k$ times, and substitute $t = 0$, you will end up with $\mathrm{E}(X^k)$.
So if you start from $(A \exp(x) + B)^N$, then you differentiate $K$ times, you will obtain:
$$\frac{\mathrm{d}^K}{\mathrm{d}x^K} (A \exp(x) + B)^N = \sum_{i = 0}^K S(K, i) \cdot (N)_i \cdot A^i \cdot (A \exp(x) + B)^{N - i} \cdot \exp(ix)$$
Again, the formula above can be easily shown (roughly shown below) using induction following the recursion property of the Stirling second kind.
Substituting $x = 0$, then you will arrive at the same equation.
We will prove that equation from the moment generating function section.
Let $f(i) = (N)_i \cdot A^i \cdot (A \exp(x) + B)^{N - i} \cdot \exp(ix)$, which in particular $f(0) = (A \exp(x) + B)^N$.
Then,
$$\frac{\mathrm{d}f(i)}{\mathrm{d}x} = (N)_{i + 1} \cdot A^{i + 1} (A \exp(x) + B)^{N - i - 1} \exp((i+1)x) + i \cdot (N)_i \cdot A^i \cdot (A \exp(x) + B)^{N - i} \cdot \exp(ix)$$
Substitute them back using $f$:
$$\frac{\mathrm{d}f(i)}{\mathrm{d}x} = f(i + 1) + i \cdot f(i)$$
Now write:
$$\frac{\mathrm{d}^k}{\mathrm{d}x^k} (A \exp(x) + B)^N = \sum_{i = 0}^k c_{k, i} \cdot f(i)$$
Differentiate it once, then you will get:
$$\frac{\mathrm{d}^{k+1}}{\mathrm{d}x^{k+1}} (A \exp(x) + B)^N = \sum_{i = 0}^{k+1} (c_{k, i - 1} + i \cdot c_{k, i}) \cdot f(i)$$
And notice that $c_{k + 1, i} = c_{k, i - 1} + i \cdot c_{k, i}$ is actually the same recurrence as the Stirling number of the second kind, which roughly end the proof.