This was a really nice problem, probably the most difficult one on Codechef that I managed to solve.

My solution is very similar to what triplem has already described:

We are given an integer Q and a D-degree polynomial P(), and we want to calculate S(N) mod M for a large N.

S(N) = P(0) * Q^0 + P(1) * Q^1 + … + P(N) * Q^N

Since P() is a polynomial of degree at most D, the (D+1)-th derivative of P would be zero, this gives us the following relation:

\sum_(i = 0 to D + 1) (-1)^i * C(D + 1, i) * P(n - i) = 0, for all n > D, i.e.

P(n) = \sum_(i = 0 to D) (-1)^i * C(D + 1, i + 1) * P(n - i - 1)

Here C(i, j) represents the binomial coefficient.

If we define X(n) = P(n) * Q^n, then

X(n) = \sum_(i = 0 to D) (-1)^i * C(D + 1, i + 1) * P(n - i - 1) * Q^(i + 1),

Finally, if we add all the X(i)’s we get

S(n) = \sum(i = 0 to D) (-1)^i * C (D + 1, i + 1) * S(n - i - 1) * Q^(i + 1) + c,

where c = \sum_(i = 0 to D) (-1)^i * C(D + 1, i) * S(D - i) * Q^i

We can further expand S(n - i)’s until, we have an expression entirely in terms of S(0), S(1), …, S(D)

S(n) = \sum_(i = 0 to D) (-1)^i * C(n - D - 1 + i, i) * C(n, D -i) * S(D - i) * Q^(n - D + i) +

```
c * \sum_(i = 0 to n - D - 1) C(D + i, D) * Q^i
```

The first sum has only (D + 1) terms, and can be calculated in O (D + log n) time. Since M is not divisible by any number in [2, D + 14], the binomial coefficients involved can be calculated easily using inverse factorial in amortized O (1) time. Also c, can be calculated in O (D) time.

The second summation is the problem, as it has O (n) terms. Let us denote it by T (n, D)

T(n, D) = \sum_(i = 0 to n - D - 1) C(D + i, D) * Q^i

Luckily, there is a recurrence for T(n, D) in terms of D.

T(n, 0) = (Q^n - 1) / (Q - 1), and

T(n, D) = (C(n, D) * Q^(n - D) - T(n, D - 1)) / (Q - 1).

Ideally, using this we should be able to compute T(n, D) in O (D + log n) time. However, this computation involves division by (Q - 1), and there is no guarantee that (Q - 1) has a multiplicative inverse in mod M.

First, it may be possible that Q = 1, this case however turns easy as in this case

T(n, D) = C(n, D + 1), so we can compute it directly without using the recurrence.

If (Q - 1) is coprime to M, then we can compute its inverse, and T(n, D) can be calculated easily.

The only difficult part is when (Q - 1) is not coprime to M.

As described in the editorial, we can split M into two parts:

M = M1 * M2, where M1 is coprime to (Q - 1), and there exist a small k such that M2 divides

(Q - 1)^k. Based on the constraints in the problem we can deduce that k <= 14.

T(n, D) mod M1 can be calculated easily.

In order to compute T(n, D) mod M2, we instead compute T(n, D) mod (Q - 1)^k which can be used easily to compute the former.

If we look at the recurrence for T(n, D), we can easily notice how to compute T(n, D) mod (Q - 1).

T(n, D + 1) = (C(n, D + 1) * Q^(n - D - 1) - T(n, D)) / (Q - 1),

Since T(n, D + 1) is an integer, (Q - 1) must divide the numerator

This means T(n, D) = C(n, D + 1) * Q^(n - D - 1) mod (Q - 1)

Now we write the expression for T(n, D + 2), we can compute T(n, D) mod (Q - 1)^2

T(n, D) = (C(n, D + 1) - C(n, D + 2)) * Q^(n - D - 1) + C(n, D + 2) * Q^(n - D - 2) mod (Q - 1)^2

In general,

T(n, D) = \sum_(i = 1 to k) (\sum_(j = i to k) (-1)^(j - i) * C(j - 1, j - i) * C(n, D + j)) * Q^(n - D - i)

mod (Q - 1)^k

Since k <= 14, we can still compute involved binomial coefficients easily modulo M (all denominators have multiplicative inverses).

Hence, the overall complexity is O (D + lg N) assuming that operation modulo M can be done in O (1) time.

I had an overflow bug in my code, and it took me a while figure that out, only after finding that the test case

where my code was failing has a value of M, 998005893107997601, which is awfully close to 10^18.