Description

B 君有两个好朋友，他们叫宁宁和冉冉。有一天，冉冉遇到了一个有趣的题目：输入三个非负整数 $b,d,n$，求

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

其中 $p=7,528,443,412,579,576,937$

Input Format

一行三个非负整数 $b$，$d$，$n$。

Output Format

一行一个数表示模 $7,528,443,412,579,576,937$ 之后的结果。

3 13 5

393

5 29 114514

4997196309027367968

Hint

保证 $0<b^2 \le d<(b+1)^2 \le 10^{18}$，$n \le 10^{18}$，并且 $b\equiv 1\pmod 2$，$d\equiv 1\pmod 4$。