配点 : 100 点
問題文
\mathbb{N}为所有正整数的集合, 定义f:\mathbb{N}\rightarrow\mathbb{N} 如下。 给定
f(x):=\begin{cases}f\left(\frac xP\right)&\text{if}\quad x\equiv 0 \pmod{P}\\x&\text{otherwise}\end{cases}
整数 (P,Q,L,R) ,在一行中打印以下值。 请输出
\text{ans}=\displaystyle\left(\prod_{i=L}^{R}f(i)\right) \ \bmod Q
制約
- 所有输入均为整数
- 2\leq P, Q \leq 10^7
- 1\leq L\leq R\leq 10^{18}
入力
输入是按以下格式从标准输入给出的。
P Q L R
出力
\displaystyle\left(\prod_{i=L}^{R}f(i)\right) \ \bmod Q \ 的值。
入力例 1
2 5 6 9
出力例 1
4
- f(6)\times f(7)\times f(8)\times f(9)=3\times 7\times 1\times 9=189 因此,要输出的值为 请注意 189 \bmod 5=4 。
入力例 2
3 3 57 61
出力例 2
1
- f(57)=19 。
入力例 3
65536 2 7 9
出力例 3
0
入力例 4
7878 78787 1234 56789
出力例 4
14334
入力例 5
2 4 1 81357343004
出力例 5
1