#P5543. 幂次求和

    ID: 4546 传统题 1000ms 256MiB 尝试: 61 已通过: 6 难度: 7 上传者: 标签>CF2200提高连续点值插值阶乘逆元预处理前后缀分解快速幂快速乘防溢出一维前缀和同余的加减乘运算

幂次求和

Description

$m^{\wedge} k+(m+1)^{\wedge} k+(m+2)^{\wedge} k+\ldots . .+n^{\wedge} k$ 模 pp 的余数(p是质数)

输入格式

一行包含 4 个正整数 k,n,m,pk, n, m, p

输出格式

如题所示

1 675126 113079 817892521
673541250

限制

$\begin{aligned} & \mathrm{K}\leq10^{12 }\\ & \mathrm{~N}, \mathrm{M}, \mathrm{P}\leq10^{12} \\ & \mathrm{~N}-\mathrm{M}\leq 5000 或者 k \leq 2000\end{aligned}$