Problem Description

Given four integers \( X, P, A, B \) where \( 1 \leq X \). Here, \( P \) is a prime number. Find the minimum value of the remainder when \( X^i \) (for \( A \leq i \leq B \)) is divided by \( P \).

The input for this problem, excluding the non-affecting sample input #1, was generated using this C++ program. The first argument of the program used for initializing the pseudorandom number generator was an integer between 1 and 10,000. The \( i \)-th line (where \( 1 \leq i \leq 10,000 \)) in this file matches the output when the first argument of the input generation program is \( i \). That is, the given test cases, excluding sample input #1, match one of the lines in this file.

Input Format

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

\( X \) \( P \) \( A \) \( B \)

• The first line contains four integers \( X, P, A, B \) separated by spaces where \( 1 \leq X \). Here, \( P \) is a prime number.

Output Format

Output the minimum value of the remainder when \( X^i \) (for \( A \leq i \leq B \)) is divided by \( P \) on a single line.

Sample Input and Output

Sample Input #1

2 11 3 9

Sample Output #1

3

Sample Input #2

15 7159 12 12818

Sample Output #2

1

Sample Input #3

1400884 50141599 4 458568

Sample Output #3

114

Sample Input #4

1591755 291456379 215 1223

Sample Output #4

96324

Notes/Hints

Sample Explanation 1

The remainders of \( X^i \) (for \( A \leq i \leq B \)) when divided by \( P \) are \( 8, 5, 10, 9, 7, 3, 6 \), so the minimum value is \( 3 \). This input was not created using the input generation program and does not affect the score.

Sample Explanation 2

This input was generated by giving the first argument of the input generation program as \( 1 \).

Sample Explanation 3

This input was generated by giving the first argument of the input generation program as \( 3 \).

Sample Explanation 4

This input was generated by giving the first argument of the input generation program as \( 25 \).

见题面 Input 部分

见题面 Output 部分