Problem Description

Given $n, a, k$, compute:

Output the answer modulo $10^9 + 7$.

Input Format

Input one line with three non-negative integers $n, a, k$. Here $n, a \ge 1$.

Output Format

Output one line with one integer representing the answer.

3 4 0

84

3 10 1

3210

3 9 2

6894

Hint

For $100\%$ of the testdata, $n \le 10^{18}$, $a \le 10^9$, and $k \le 2000$.

Translated by ChatGPT 5