10451: #2106. 「JLOI2015」有意义的字符串

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

$$[(\frac{b+\sqrt{d}}{2}{)}^n]\mathrm{mod}7528443412579576937$$

输入格式

一行三个整数 $b,d,n$

输出格式

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

样例

样例输入

1 5 9

样例输出

76

数据范围与提示

其中 0<b2≤d<(b+1)2≤1018, n≤10180<b^2 \leq d <(b+1)^2 \leq 10^{18}, \ n \leq 10^{18}0<b​2​​≤d<(b+1)​2​​≤10​18​​, n≤10​18​​，并且 $b\mathrm{mod}2=1,d\mathrm{mod}4=1$