작은 바샤를 위한 큰 수

바샤는 생일에 정수 두 개를 선물로 받았다.

첫 번째 수는 숫자 $D$를 $N$번 이어 쓴 수이고, 두 번째 수는 같은 숫자 $D$를 $M$번 이어 쓴 수이다.

바샤는 두 수의 최대공약수를 구하고 싶었지만 수가 너무 커서 계산할 수 없었다. 바샤를 도와 받은 두 수의 최대공약수를 구하라.

최대공약수는 두 수를 나머지 없이 모두 나누는 가장 큰 자연수이다.

첫째 줄에 공백으로 구분된 정수 $N$과 $M$이 주어진다 ($1 \leq N, M \leq 10^{18}$). 각각 첫 번째 수와 두 번째 수의 자릿수이다. 둘째 줄에는 정수 $D$가 주어진다 ($1 \leq D \leq 9$). $D$는 두 수를 이루는 숫자이다.

최대공약수를 십진수로 나타냈을 때 자릿수가 $10^6$자리 이하이면 최대공약수 자체를 출력한다. 그렇지 않으면 최대공약수의 마지막 $10^6$자리를 출력한다. 앞에 0을 붙이지 않는다.