[JLOI2015] 有意义的字符串

题目描述

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$

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

3 13 5

输出样例 #1

393

输入样例 #2

5 29 114514

输出样例 #2

4997196309027367968

说明

保证 $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$。