I. Euclid's Algorithm
time limit per test
1 second
memory limit per test
256 mebibytes
input
standard input
output
standard output

Euclid's algorithm is one of the oldest algorithms known to mankind. It is used to find greatest common divisor of two given numbers. Your program should also take two numbers and find a greatest common divisor. And may Euclid be with you.

I give you two positive integers $$$d$$$ and $$$k$$$. Your task is to find the largest integer that divides $$$(a+d)^{k} - a^{k}$$$ for every positive integer $$$a$$$.

Input

The only line contains two integers $$$d$$$ and $$$k$$$ ($$$1 \le d, k \lt 10^{100}$$$).

Output

Print a single integer — the largest integer that divides $$$(a+d)^{k} - a^{k}$$$ for every positive integer $$$a$$$.

Example
Input
2 2
Output
4