問題文

$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$ 引数は $1$ 以上 $10,000$ 以下の整数を用いました。このファイルの $i$ 行目 $(1 ≦ i ≦ 10,000)$ は、入力生成プログラムの第 $1$ 引数が $i$ であるときの出力と一致します。すなわち、与えられるテストケースは入力例 $1$ を除いて、このファイルのいずれかの行と一致します。

入力例1Copy

2 11 3 9

出力例1Copy

3

$X^i (A ≦ i ≦ B)$ を $P$ で割った余りは $8, 5, 10, 9, 7, 3, 6$ であるので、最小値は $3$ である。 この入力は入力生成プログラムを用いて作られたものではないので、得られる得点に影響しない。

入力例2Copy

15 7159 12 12818

出力例2Copy

1

この入力は入力生成プログラムの第 $1$ 引数に $1$ を与えて生成した。

入力例3Copy

1400884 50141599 4 458568

出力例3Copy

114

この入力は入力生成プログラムの第 $1$ 引数に $3$ を与えて生成した。

入力例4Copy

1591755 291456379 215 1223

出力例4Copy

96324

この入力は入力生成プログラムの第 $1$ 引数に $25$ を与えて生成した。