Grox's Sequence V A¶

Indicative time limit: 0.5 seconds.
Actual limit: twice the slowest per-case median of the reference program on the target judge, rounded up to a multiple of 0.5 seconds.
Memory limit: 512 MB.
Reference environment and measurements

Story¶

What do you believe? And how much are you willing to risk on that belief? Would you risk your existence, and the existence of your species, on a hunch? A whim? The word of a prophet a thousand years dead?

— Spore, Book of Science Pt. 1

Your persistent efforts finally bring an alliance with the Grox. At the same moment, every other civilization in the galaxy declares war on you!

After billions of Spore years, the Grox have finally made a friend, and they treasure that friendship. You discover that they are no longer as cold as they once seemed: they feel joy, anger, sorrow, and delight, and they can laugh. As a gift, they construct a sequence for you.

The whole sequence is far too long, so you decide to calculate its characteristic value and send that value back to your home planet.

Formal Problem Statement¶

Given nonnegative integers \(n,k\) and a positive integer \(p\) , define a sequence of length \(n+1\) by

\[ a_i=i^k\binom ni\qquad(0\le i\le n) \]

For this problem, \(0^0=0\) ; the zeroth power of any other integer is \(1\) . Compute the characteristic value

\[ S=\left(\sum_{i=0}^n a_i\right)\bmod p \]

Report its least nonnegative residue. The decimal integer \(n\) may not fit in ordinary integer types. The modulus \(p\) need not be prime.

Input Format¶

One line contains the decimal integers \(n,k,p\) .

Output Format¶

Output the integer \(S\) on one line.

Samples¶

Sample 1¶

Input¶

10 103 10007

Output¶

Sample 2¶

Input¶

10 0 10007

Output¶

Sample 3¶

Input¶

3 1 8

Output¶

Sample Explanation¶

In sample 2, only \(i=0\) contributes nothing, so the result is \(2^{10}-1=1023\) . In sample 3, the sum is \(3+6+3=12\) , whose residue modulo \(8\) is \(4\) .

Constraints and Guarantees¶

For 100% of the data:

\(0\le n\le10^{1000}\) ; \(0\le k\le3000\) ; \(1\le p\le2\times10^9\) .

Score share	Additional conditions
100%	None