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

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

\bigg [ \Big ( \frac{b+ \sqrt{d}}{2} \Big )^n \bigg ]\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