18496번 - Euclid’s Algorithm 다국어

문제

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.

입력

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

출력

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

제한

힌트