暂无测试数据。

出好题是每个 OIer 都向往着的，而验题的过程也会给机房带来不少欢乐。msannuoi 机房中，时常会出现出题人被验题人 D，或者验题人的错误做法被出题人 D 的有趣场景。

SS 出了一道数学题，但想要验题的S却发现自己只会暴力分——毕竟 S 是一个对数学一窍不通的 OIer。在口胡一通发现毫无结果后，他决定场外求助。于是，他找到了你，希望你能帮他优化一下他的做法。

对于 SS 在题中的要求，S 的代码实现如下：

inline int solve (int l, int r, int p) {
    int ans = 1;
    for (int i = l; i <= r; i++) {
          for(int j = 2; p % j != 0 ||  i % j != 0; j++) {
            if(j > p){
                ans = i * (long long)ans % p;
                break;
            }
        }
    }
    return ans;
}

你需要实现一个函数，与其功能相同。注意：S 只写了int范围内的部分分，但你函数所能解决的范围应按照本题数据范围计算。

输入格式

一行三个整数 $l,r,p$，含义见题目描述。

输出格式

一个整数 $ans$，含义见题目描述。

数据范围

对于$20\%$的数据，$l,r\le 10^6$。

对于$30\%$的数据，$\frac{r}{p} \le 10^7$。

对于$60\%$的数据，$l,r\le 10^{18}$。

对于$80\%$的数据，$1\le l,r \le 10^{1000}$。

对于$100\%$的数据，$1 \le l \le r \le 10^{10^6},2 \le p \le10^6$

2 10 5

1

1 9260817 2333333

220739