问题文

给定4个整数 $X, P, A, B (1 ≦ X < P < 2^{31}, 0 ≦ A ≦ B < 2^{31})$。其中，$P$ 是素数。求 $X^i (A ≦ i ≦ B)$ 模 $P$ 的最小值。

此问题的输入除了不影响得分的输入示例1之外，其余输入均由此C++程序生成。生成擬似随机数的程序的第一个参数使用的是1到10,000之间的整数。此文件中的第 $i$ 行 $(1 ≦ i ≦ 10,000)$ 与输入生成程序的第1个参数为 $i$ 时的输出相匹配。也就是说，除了示例1之外的测试用例与该文件中的某一行匹配。

输入

输入从标准输入中以以下格式给出。

$X$ $P$ $A$ $B$

• 第1行包含4个整数 $X, P, A, B (1 ≦ X < P < 2^{31}, 0 ≦ A ≦ B < 2^{31})$，以空格分隔。其中，$P$ 是素数。

输出

将 $X^i (A ≦ i ≦ B)$ 模 $P$ 的最小值输出为1行。

输入样例1

2 11 3 9

输出样例1

3

$X^i (A ≦ i ≦ B)$ 模 $P$ 的结果为8、5、10、9、7、3、6，其中最小值为3。该输入不是由输入生成程序生成的，因此不会影响得分。

输入样例2

15 7159 12 12818

输出样例2

1

该输入是由输入生成程序的第1个参数设置为1生成的。

输入样例3

1400884 50141599 4 458568

输出样例3

114

该输入是由输入生成程序的第1个参数设置为3生成的。

输入样例4

1591755 291456379 215 1223

输出样例4

96324

该输入是由输入生成程序的第1个参数设置为25生成的。