Harmonic Series Modulo a Prime

In mathematics, the harmonic series is the following sum:

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

The series has many remarkable properties. It diverges, and the sum of its first $n$ terms approaches $\ln(n) + \gamma$ as $n$ goes to infinity, where $\gamma$ is the Euler-Mascheroni constant.

Tor does not care much for mathematical analysis, so the remarkable properties of the harmonic series do not interest him much. Out of boredom, Tor invented a new mathematical object and named it the harmonic series modulo a prime $p$.

Tor defines the harmonic series modulo a prime $p$ as the following sum:

$\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$

For an integer $x \in [1; p-1]$, Tor calls $\frac{1}{x}$ the integer $y \in [1; p-1]$ such that $x \cdot y \equiv 1 \pmod p$. If $p$ is prime, then for every such $x$ there is exactly one suitable $y$, and this can be proven.

Tor wants to know the value of the sum of terms from $l$ to $r$, that is, $\sum_{i=l}^{r} \frac{1}{i} \pmod p$.

The first line contains three integers $l$, $r$, and $p$ ($1 \le l \le r < p$, $r - l < 2 \cdot 10^7$, $p \le 10^9$, $p$ is prime).

Print one integer, the answer to the problem. All arithmetic operations in this problem are performed modulo $p$.

A natural number $x$ is prime if $x \ne 1$ and $x$ has no divisors other than $1$ and $x$.