Grox's Sequence V B¶

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: 128 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\) , let \(P=1005060097\) . Define

\[ 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

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

Report the least nonnegative residue.

Input Format¶

One line contains \(n,k\) .

Output Format¶

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

Samples¶

Sample 1¶

Input¶

10 103

Output¶

14606983

Sample 2¶

Input¶

10 0

Output¶

Sample 3¶

Input¶

0 0

Output¶

Sample Explanation¶

The answer in sample 2 is \(2^{10}-1=1023\) . In sample 3, the only term is \(0^0\binom00=0\) .

Constraints and Guarantees¶

For 100% of the data:

\(0\le n\le10^9\) ; \(0\le k\le100000\) .

Score share	Additional conditions
100%	None