Description

蝳最近在翻自己三年前的数学练习册的时候发现了一道题，觉得很有意思：

定义 $S(n,m)=\sum\limits_{i=1}^{m} \varphi(n\times i)$ ，给定 $n$ 和 $m$ 的值，求 $S(n,m)$ 在模 $p$ 意义下的值。

$\color{grey}{wlzhouzhuan}$ 数学很差，所以只好丢给您来解答。

注：$\varphi$ 是欧拉函数。具体地，若 $n=p_1^{a_1}p_2^{a_2} ... p_k^{a_k}$ ，则 $\varphi(n)=n\times \prod\limits_{i=1}^{k} (1-\frac{1}{p_i})$ 。

Input

输入三个数 $n$, $m$ 和 $p$ ，不保证 $p$ 是质数。

Output

输出 $S(n,m) \% p$ 的值。

Samples

• Input

1 2 1145141919

• Output

2

Constriants

本题采用 $subtask$ 。

子任务 $1$ （10分）：$1\le n,m\le 500$ ，保证 $p$ 是质数；

子任务 $2$ （20分）：$1\le n,m\le 5000$ ，保证 $p$ 是质数；

子任务 $3$ （20分）：$n=1$ ，不保证 $p$ 是质数；

子任务 $4$ （10分）：$m=1$ ，不保证 $p$ 是质数；

子任务 $5$ （30分）：$1\le n,m\le 10^{9}$ ，保证 $p$ 是质数；

子任务 $6$ （10分）：$1\le n,m\le 10^{9}$ ，不保证 $p$ 是质数。

对于 $100\%$ 的数据，$10^8\le p\le 10^9 + 7$ 。