8540: Ice Drinking

One day NIO was very thirsty, so he went to the ice-drinking room and ordered n different drinks, each with a unique ingredient.

The owner thought NIO's request was too weird, so he asked NIO, "How can you eat like this?" However, NIO just responded with "none of your business". The ice-drinking room owner was very angry, so he decided to add the n ingredients to NIO's n drink at random while ensuring that each cup of drink will have exactly one ingredient.

NIO discovered what the ice-drinking owner was trying to do. Given a natural number k, he wants to know in advance what the expected value of x^k is, if we let x denote the number of cups with the correct ingredient.

Since Nio does not like fractions, he only wants to know the value of the result modulo 862118861.

The only line of input contains two natural numbers n,k in order, where 1≤n≤10¹⁸, 0≤k≤n+5×10³.

Output a natural number in one line, denoting the answer modulo 862118861.

3 4

14

Let 1, 2, 3 denote the three ingredients. There are six possible results.

1 2 3: x=3,x^k=81.
1 3 2, 2 1 3, 3 2 1: x=1,x^k=1.
2 3 1, 3 1 2: x=0,x^k=0.
Thus E(x^k)=(81+3)/6=14.