Description

Mr. B has two good friends, named Ningning and Ranran. One day, Ranran encountered an interesting problem: given three non-negative integers $b,d,n$, compute

$$\left\lfloor \left ( \frac{b+\sqrt{d}}{2} \right ) ^n \right\rfloor \bmod p,$$

where $p=7,528,443,412,579,576,937$.

Input Format

One line containing three non-negative integers $b$, $d$, and $n$.

Output Format

Output a single integer denoting the result modulo 7,528,443,412,579,576,937.

3 13 5

393

5 29 114514

4997196309027367968

Hint

It is guaranteed that $0<b^2 \le d<(b+1)^2 \le 10^{18}$, $n \le 10^{18}$, and $b\equiv 1\pmod 2$, $d\equiv 1\pmod 4$.

Translated by ChatGPT 5