시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB299644118.721%

문제

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 − ak for every positive integer a.

입력

The only line contains two integers d and k (1 ≤ d, k < 10100).

출력

Print a single integer — the largest integer that divides (a + d)k − ak for every positive integer a.

예제 입력 1

2 2

예제 출력 1

4