Description

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

输入格式

一行包含 4 个正整数 $k, 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}$