Since the formula is \sum _{k=0} ^{K} (k^m-(k-1)^m)(k^n-(k-1)^n)

If we write the inner part as a polynomial in k (Which we can do by just expanding it from the binomial theorem formula) we just need to find \sum _{k=0} ^{K} k^i for all i from 0 to m+n.

The fft is used for \sum _{k=0} ^{K} k^i part as we can find that using bernoulli numbers (Faulhaber’s formula). The formula and method for the same is mentioned here. https://codeforces.com/blog/entry/60756. I used the method he mentioned in his reply to the first comment which convolves A and B (can use fft again for this, refer the post for what’s A and B). For the code to find Bernoulli numbers fast you can refer to MAY18A editorial for the problem SERSUM : SERSUM - Editorial (reupload). This is mentioned in the codeforces blog but this editorial has a clearer and longer explanation.

Interpolation solutions seem way simpler though.