시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 1024 MB48221436.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

1 5 7

예제 출력 1

1

예제 입력 2

3 10 31

예제 출력 2

4

노트

Натуральное число $x$ называется простым, если оно не равно $1$ и у него нет делителей, отличных от $1$ и $x$.