소수 p를 법으로 하는 조화급수

수학에서 조화급수는 다음 합을 말한다.

$\sum_{k=1}^{\infty} \frac{1}{k} = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \ldots$

이 급수에는 여러 흥미로운 성질이 있다. 급수는 발산하며, 처음 $n$개 항의 합은 $n$이 무한대로 갈 때 $\ln(n) + \gamma$에 가까워진다. 여기서 $\gamma$는 오일러-마스케로니 상수이다.

토르는 해석학을 그리 좋아하지 않아서 조화급수의 흥미로운 성질에는 별 관심이 없다. 대신 토르는 심심풀이로 새로운 수학 대상을 만들고, 이를 소수 $p$를 법으로 하는 조화급수라고 이름 붙였다.

토르는 소수 $p$를 법으로 하는 조화급수를 다음 합으로 정의한다.

$\sum_{i=1}^{p-1} \frac{1}{i} \pmod p = \left(\frac{1}{1} + \frac{1}{2} + \ldots + \frac{1}{p-2} + \frac{1}{p-1}\right) \pmod p$

정수 $x \in [1; p-1]$에 대해 토르는 $x \cdot y \equiv 1 \pmod p$를 만족하는 정수 $y \in [1; p-1]$을 $\frac{1}{x}$라고 부른다. $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$를 법으로 수행한다.

자연수 $x$가 소수라는 것은 $x \ne 1$이고 $1$과 $x$ 이외의 약수가 없다는 뜻이다.