#110. czq的模法数列

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

题目描述

如果某题的整数答案过大,超出了一般类型的表示范围。而良心出题人又不打算考察你高精度整数的运用,他们会要求你输出答案对取模的结果。的常见取值有等。

给定一个整数,任意一个整数,一定存在等式,其中, 是整数,且 

除以的商,除以的余数。就是取模的结果,记做

对于正整数和正整数,C++定义的%运算:,%和的优先级与乘除运算同级。

需要注意在为负数时,C++的%运算的答案实际上为 , 而不是我们期望的。一个通用的取模写法是(a%mod+mod)%mod

模运算有着很好的性质:

在要求答案对取模的时候,你应当利用模运算的性质,最好在每次运算之后进行取模,以避免答案超出变量所能表示的范围上限。同时,负数取模需要额外注意。


给定一个长度为,首项为1,公比为的等比数列,求其模意义下的和。

输入格式

输入仅一行,为三个由空格隔开的整数

输出格式

仅一个整数,为答案。

样例

样例输入1

10 2 1000

样例输出1

23

样例解释1

样例输入2

114 -514 1919810

样例输出2

107369

数据范围与提示

提示:

负数 取模可以写成这样 ((x%p)+p)%p.

如果 WA 了,建议检查数据类型选用是否合适,以及是否及时取模。检查是否会出现溢出的情况。

如果 TLE 了,试试看能不能在累乘 的时候顺手统计答案?