| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 1024 MB | 48 | 22 | 14 | 36.842% |
Гармоническим рядом в математике называется следующая сумма:
$\sum_{k = 1}^{\infty} = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \ldots$.
Данный ряд обладает многими замечательными свойствами. Он расходится, а сумма первых $n$ его членов стремится к $\ln(n) + \gamma$ (где $\gamma$ --- константа Эйлера — Маскерони) при стремлении $n$ к бесконечности.
Тор не очень любит математический анализ, поэтому его не очень интересуют факты про замечтельные свойства гармонического ряда. Зато Тор от скуки придумал новый математический объект и назвал его гармоническим рядом по простому модулю $p$.
Гармоническим рядом по простому модулю $p$ Тор называет следующую сумму:
$\sum_{i = 1}^{p - 1} \frac{1}{i} \pmod p = (\frac{1}{1} + \frac{1}{2} + \ldots + \frac{1}{p - 2} + \frac{1}{p - 1}) \pmod p$.
Числом $\frac{1}{x}$ для целого $x \in [1; p - 1]$ по простому модулю $p$ Тор называет такое целое число $y \in [1; p - 1]$, что $x \cdot y \equiv 1 \pmod p$. Можно доказать, что если $p$ --- простое число, то для любого $x$, удовлетворяющего ограничению выше, найдётся ровно один подходящий $y$.
Тору стало интересно, чему равна сумма членов ряда от $l$ до $r$, то есть чему равна сумма $\sum_{i = l}^{r} \frac{1}{i} \pmod p$.
В первой строке задано три целых числа $l$, $r$ и $p$ ($1 \le l \le r < p, r - l < 2 \cdot 10^7, p \le 10^9$, p --- простое).
Выведите одно целое число --- ответ на задачу. Обратите внимание, что все арифметические операции в данной задаче выполняются по модулю $p$.
1 5 7
1
3 10 31
4
Натуральное число $x$ называется простым, если оно не равно $1$ и у него нет делителей, отличных от $1$ и $x$.