시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 109 43 32 45.070%

문제

세 소수 p1, p2, p3을 이용해서 해밍 수열 H(p1, p2, p3), i = 1... 을 정의할 수 있다.

해밍 수열 H(p1, p2, p3)은 소인수가 p1, p2, p3로만 이루어진 자연수의 오름 차순 목록이다.

예를 들어, H(2, 3, 5) = 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, ... 이고, 5번째 숫자는 6이다.

입력

첫째 줄에 p1, p2, p3, i가 주어진다. 네 숫자는 1018보다 작다.

출력

H(p1, p2, p3)의 i번째 숫자를 출력한다. 출력하는 숫자는 1018보다 작다.

예제 입력

7 13 19 100

예제 출력

26590291

힌트