#P4002. [JLOI2015]有意义的字符串

    ID: 3203 传统题 1000ms 128MiB 尝试: 1215 已通过: 405 难度: 6 上传者: 标签>难度分类提高线性代数与代数线性递推矩阵快速幂数论向下取整与向上取整快速乘防溢出CF2000

[JLOI2015]有意义的字符串

[JLOI2015] 有意义的字符串

题目描述

B 君的朋友冉冉拿到三个非负整数 b,d,nb,d,n,请你帮他计算

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

输入格式

输入一行三个非负整数 b,d,nb,d,n。

输出格式

输出一行一个整数,表示所求余数。

样例 #1

样例输入 #1

1 5 9

样例输出 #1

76

数据范围

对于全部数据,0<b2≤d<(b+1)2≤10180<b^2\le d<(b+1)^2\le10^{18},0≤n≤10180\le n\le10^{18},b≡1(mod2)b\equiv1\pmod 2,d≡1(mod4)d\equiv1\pmod 4。

另外保留原题样例所用的特例 (b,d)=(1,5)(b,d)=(1,5),该特例不受上式 d<(b+1)2d<(b+1)^2 的限制,仍按同一公式计算。