题目描述

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

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

输入格式

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

输出格式

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

样例

输入：

1 5 9

输出：

76

数据范围与提示

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