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$$$.
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}$$$).
Print a single integer — the required sum modulo $$$676767639049076737$$$.
1 1 5
5
2 2 2
1
46 32 2023
219967572955941990