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 $A$ of at most $N$ integers. Formally, $1\leq |A|\leq N$.
The array elements should be positive integers at most $M$. Formally, $1\leq A_i\leq M$ for each $1\leq i\leq |A|$.
Each element of the array (except the first one) should be divisible by the previous element. Formally, $A_i\mid A_{i+1}$ should hold for each $1\leq i<|A|$.
After creating such an array, Mocha raises the last element of the array to the power $K$. 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 $10^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 $N$ — the limit on the size of the array, $M$ — the limit on the array elements, $K$ — the power Mocha raises the last element of each array to.
These integers satisfy $1\leq N,M\leq 10^{9}$ and $0\leq K\leq 100$.
Print a single line containing the password, which is the sum (modulo $10^9+7$) of the last elements of all possible arrays satisfying the aforementioned conditions, raised to the power $K$.
Input | Output |
---|---|
1 3 0 | 3 |
There are only three possible arrays in this case: $[1],[2],[3]$. The power to raise to is $K=0$. So the password would be $1^0+2^0+3^0=3$. |
Input | Output |
---|---|
2 2 3 | 26 |
There are five possible arrays: $[1],[2],[1,1],[1,2],[2,2]$. The power to raise to is $K=3$. So the password would be $1^3+2^3+1^3+2^3+2^3=26$. |
Input | Output |
---|---|
314 15 92 | 168177682 |
Remember to reduce the result modulo $10^9+7$. |