세 소수 p₁, p₂, p₃을 이용해서 해밍 수열 H(p₁, p₂, p₃), i = 1... 을 정의할 수 있다.

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

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

입력 형식

첫째 줄에 p₁, p₂, p₃, i가 주어진다. 네 정수는 10¹⁸보다 작다.

출력 형식

H(p₁, p₂, p₃)의 i번째 수를 출력한다. 출력하는 수는 10¹⁸보다 작다.

예제 입력

7 13 19 100

예제 출력

26590291