暂无测试数据。

蒜头君在刷题的过程中遇到了困难，经过长时间的钻研，他写出了很多很多版本的解题程序，但是全部 Wrang answer 了。现在他怀疑是不是自己理解错了题意，但是现在他找不到原题了，只能找到自己最早的程序的关键函数以及题目的数据范围，函数返回值为结果，结果正确，但是时间超时了。

函数如下：

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;
}

请你根据上述函数，编写一个优化程序，实现与上述函数相同的功能。

注意：上述函数使用 int 类型，但你的函数所能解决的数据应该按照本题的数据范围计算。

输入格式

输入共一行，以空格隔开的三个正整数 $l, r, p$，分别作为上述函数的参数。

输出格式

输出共一行，一个整数 $ans$，表示函数返回的正确结果。

数据范围

对于 $20\%$ 的数据，$1\leq l\leq r \leq 10^6$；

对于 $30\%$ 的数据，$1\leq \frac{r}{p} \leq 10^6$；

对于 $60\%$ 的数据，$1\leq l\leq r \leq 10^{18}$；

对于 $80\%$ 的数据，$1\leq l\leq r \leq 10^{1000}$；

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

2 10 5

1

1 9260817 233333

73906