問題文

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

入力例 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