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.

  • He creates a non-empty array AA of at most NN integers. Formally, 1AN1\leq |A|\leq N.

  • The array elements should be positive integers at most MM. Formally, 1AiM1\leq A_i\leq M for each 1iA1\leq i\leq |A|.

  • Each element of the array (except the first one) should be divisible by the previous element. Formally, AiAi+1A_i\mid A_{i+1} should hold for each 1i<A1\leq i<|A|.

  • After creating such an array, Mocha raises the last element of the array to the power KK. This gives him 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?

Input

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.

Output

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.

Samples

InputOutput
1 3 0
3

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.

InputOutput
2 2 3
26

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.

InputOutput
314 15 92
168177682

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


Submit

Login to submit.

Statistics

67% Solution Ratio
YouKnowWhoEarliest, 8M ago
Md.823970Fastest, 8.9s
YouKnowWhoLightest, 10 MB
YouKnowWhoShortest, 2889B
Toph uses cookies. By continuing you agree to our Cookie Policy.