**PROBLEM LINK**:

Practice

Contest, div. 1

Contest, div. 2

**Author:** Rezwan Arefin

**Tester:** Ildar Gainullin

**Editorialist:** Oleksandr Kulkov

**DIFFICULTY**:

MEDIUM-HARD

**PREREQUISITES**:

Fast Fourier transform, basics of calculus, polynomials

**PROBLEM**:

You have to calculate \sum\limits_{i=0}^N \binom{p^i}{r} for given N, p and r modulo m=998\,244\,353, where r \leq 10^6.

**QUICK EXPLANATION**:

Consider P(x)=\binom{x}{r} as a polynomial of x, then you may find \sum\limits_{i=0}^N P(p^i) as:

**EXPLANATION**:

Note that P_r(x)=\binom{x}{r} is the polynomial of x of degree r, which coefficients may be calculated in O(r \log r). Indeed, for odd values P_r(x) are recalculated from P_{r-1}(x) and for even values of r we may rewrite it as follows:

And transition from P(x) to P(x-r) may be done in O(n \log n) time as well:

Where c_i are coefficients defined by some particular convolution:

Where \alpha_k = \frac{(-r)^k}{k!} and \beta_k = a_{n-k} (n-k)!, thus c_i is a simple convolution of \alpha and \beta. This convolution may be calculated as coefficients in the product of polynomials A(x) and B(x) having \alpha_k and \beta_k as their coefficients correspondingly.

That means that the whole time needed to calculate P_r(x) is:

Now that we know explicit coefficients of P(x)=\binom{x}{r}, our task is to calculate sum of P(p^i) for i from 0 to N for given polynomial P(x). Let it be that P(x) =a_0 + a_1x + \dots + a_n x^n, then:

Calculating this sum will take additional O(r \log N) of time, which makes total complexity of the solution to be equal to O(r \log rN).

**AUTHOR’S AND TESTER’S SOLUTIONS**:

Author’s solution can be found here.

Tester’s solution can be found here.