Problem Statement

$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$ を除いて、このファイルのいずれかの行と一致します。

Input

入力は以下の形式で標準入力から与えられる。

X P A B

• $1$ 行目には、$4$ つの整数 $X, P, A, B (1 ≦ X < P < 2^{31}, 0 ≦ A ≦ B < 2^{31})$ が空白区切りで与えられる。ただし、$P$ は素数である。

Output

$X^i (A ≦ i ≦ B)$ を $P$ で割った余りの最小値を $1$ 行に出力せよ。