Description

请计算对于给出的$N,M$，$a^{N}-b^{N}$与$a^{M}-b^{M}$的最大公约数。 题目保证$a,b$互质，且$a>b$

Format

Input

多组输入，两个整数$a,b,N,M$ $(1\le a,b \le 500,1\le N,M \le 50)$

Output

$a^{N}-b^{N}$与$a^{M}-b^{M}$的最大公约数。,保证结果不超过$2^{63}-1$

Samples

3 2 2 3

1