A Lazy Statement

Limits 10s, 256 MB

Milk has created an account in the newly launched social network Coffeebook. However, she cannot decide on a password for her account. So she’s asked Mocha for help (don’t ask me why she trusts Mocha this much).

Mocha has decided to make the process interesting for himself. At each step, he applies the following procedure to come up with a random number.

Mocha doesn’t want to bore himself with the same array over and over again. So at each step, he creates a new array (satisfying the above conditions), an array he hasn’t created before. He stops only when he runs out of arrays satisfying the above conditions. Then he adds up all the powers he’s extracted out of these arrays and adds them up. The result, modulo 109+710^9+7, is the password he’ll suggest to Milk.

However, soon after coming up with this plan, Mocha realizes that it will take him a long time to go through all possible arrays. He can’t do it on his own. Can you help him?


The only line of input will contain three space-separated positive integers NN — the limit on the size of the array, MM — the limit on the array elements, KK — the power Mocha raises the last element of each array to.

These integers satisfy 1N,M1091\leq N,M\leq 10^{9} and 0K1000\leq K\leq 100.


Print a single line containing the password, which is the sum (modulo 109+710^9+7) of the last elements of all possible arrays satisfying the aforementioned conditions, raised to the power KK.


1 3 0

There are only three possible arrays in this case: [1],[2],[3][1],[2],[3]. The power to raise to is K=0K=0.

So the password would be 10+20+30=31^0+2^0+3^0=3.

2 2 3

There are five possible arrays: [1],[2],[1,1],[1,2],[2,2][1],[2],[1,1],[1,2],[2,2]. The power to raise to is K=3K=3.

So the password would be 13+23+13+23+23=261^3+2^3+1^3+2^3+2^3=26.

314 15 92

Remember to reduce the result modulo 109+710^9+7.