H. Huron or Robot?
time limit per test
12 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The Legendary Huron was trying to access huronforces.com, his favorite website for solving competitive programming problems. However, the website detected some suspiciously fast mouse movements and decided that he might actually be a very talented robot.

To prove that he is a real ferret, the website presented him with a CAPTCHA. Unfortunately, instead of asking him to identify traffic lights or bicycles, the CAPTCHA gave him a combinatorics problem.

He is given three integers $$$n$$$, $$$m$$$, and $$$k$$$. Consider all possible solutions to the following sum:

$$$$$$ \sum_{i=1}^{n} x_i=k. $$$$$$

where every $$$x_i$$$ is a non-negative integer.

For each such solution, the CAPTCHA computes the following product:

$$$$$$ \prod_{i=1}^{m} x_i. $$$$$$

The Legendary Huron must find the sum of this value over all possible solutions of the equation. Help the Legendary Huron solve the CAPTCHA so he can finally access huronforces.com. Since the answer may be huge, print it modulo $$$676767639049076737$$$.

Input

The input consists of a single line containing three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le m \le n \le 10^{10}$$$ and $$$0 \le k \le 10^{10}$$$).

Output

Print a single integer — the required sum modulo $$$676767639049076737$$$.

Examples
Input
1 1 5
Output
5
Input
2 2 2
Output
1
Input
46 32 2023
Output
219967572955941990