Problem Description

Let $\mathbb{N}$ be the set of all positive integers, and define $f:\mathbb{N}\rightarrow\mathbb{N}$ as follows:

$f(x):=\begin{cases}f\left(\frac{x}{P}\right)&\text{if}\quad x \equiv 0 \pmod{P}\\x&\text{otherwise}\end{cases}$

Given integers $ (P, Q, L, R) $, output the following value in one line:

$\text{ans}=\displaystyle\left(\prod_{i=L}^{R}f(i)\right) \bmod Q$

Input Format

The input is given from the standard input in the following format:

$ P $ $ Q $ $ L $ $ R $

Output Format

Output the value of $\displaystyle\left(\prod_{i=L}^{R}f(i)\right) \bmod Q$.

Sample Input and Output

Sample Input #1

2 5
6 9

Sample Output #1

4

Sample Input #2

3 3
57 61

Sample Output #2

1

Sample Input #3

65536 2
7 9

Sample Output #3

0

Sample Input #4

7878 78787
1234 56789

Sample Output #4

14334

Sample Input #5

2 4
1 81357343004

Sample Output #5

1

Notes/Hints

Constraints

• All inputs are integers.
• $2 \leq P, Q \leq 10^7$
• $1 \leq L \leq R \leq 10^{18}$

Sample Explanation 1

• $f(6) \times f(7) \times f(8) \times f(9) = 3 \times 7 \times 1 \times 9 = 189$, so the value to output is $189 \bmod 5 = 4$.

Sample Explanation 2

• Note that $ f(57) = 19 $.

见题面 Input 部分

见题面 Output 部分