题目描述

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

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

其中$p=7528443412579576937$

输入格式

一行三个整数 b;d;n

输出格式

一行一个数表示模 7528443412579576937 之后的结果。

1 5 9

76

提示

其中 $0<b^2 \le d<(b+1)^2 \le 10^{18}$,$n \le 10^{18}$，并且 b mod 2=1,d mod 4=1