27505번 - 천국의 계단

문제

천사들이 천국에 계단을 만들고 있다.

계단을 만드는 재료는 밑면의 모양이 동일하고 높이는 $A,ドル $B$인 2ドル$종류의 직육면체로, 각 종류의 직육면체는 무한히 많이 준비되어 있다. 하나의 단을 만들 때 각 직육면체의 밑면을 밑으로 하여 재료를 위로 쌓아 올려서 만든다.

계단의 $i$번째 단의 높이가 $i$가 되도록 한다. 대신 이렇게 하면 $A,ドル $B$의 값에 따라 만들 수 없는 단이 존재할 수도 있다. 천사들은 재료를 가공하는 건 귀찮았을뿐더러 어차피 날아다닐 수 있기 때문에 만들 수 없는 단은 만들지 않기로 했다.

공사는 1번 단부터 차례대로 진행된다. 방금 막 $N$번 단의 공사를 완료했거나 $N$번 단은 만들지 않기로 결정했다고 하자. 지금까지 천사들이 만들 수 없는 단이 몇 개나 되는지 구해보자.

입력

첫째 줄에 가장 마지막에 공사가 완료되거나 만들지 않기로 결정한 단의 번호 $N$ (5ドル \le N \le 10^{14}$)과 두 종류의 직육면체의 높이 $A,ドル $B$ (2ドル \le A, B \le 10^{7}$)가 주어진다.

출력

첫째 줄에 1번 단에서 N번 단까지 천사들이 만들 수 없는 단의 개수를 출력한다.

제한

힌트