시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 7 5 5 71.429%

문제

프로 드링커 상근이는 술을 마실때, 조세퍼스 문제와 같은 순서로 술을 마신다. 조세퍼스 문제를 천 번 넘게 푼 상근이는 머리 속으로 가장 마지막에 술을 마시는 사람의 위치를 계산할 수 있다. 따라서, 같이 술을 마시는 친구들은 상근이를 이기기 위해서 술을 마시는 새로운 순서를 제시했다.

먼저, 원탁에 모두 앉는다. 총 N명이 원탁에 앉았다면, 각 사람의 번호는 0번부터 N-1번이 된다.

조세퍼스 문제와 다르게 다음 사람을 고르기 위해서 두 숫자 a와 b를 이용한다. 현재 선택된 사람의 번호가 x라면, 다음 사람의 번호는 ax2+b mod N이 된다.

가장 처음 시작하는 사람의 번호는 0번이다. 다음 사람의 번호는 위의 식을 이용해서 고른다.

각 사람은 한 번의 기회를 더 받을 수 있다. 즉, 한 번 걸리면 술을 마시는 것이 아니고, 두 번 걸렸을 때, 술을 마시는 것이다.

만약, 어떤 사람이 세 번 걸렸다면, 그 즉시 모두 자리를 박차고 일어나 집으로 간다.

N과 a, b가 주어졌을 때, 술을 마시지 않고 집으로 가는 사람의 수를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 세 숫자 N, a, b가 공백으로 구분되어져 있다. (2 ≤ N ≤ 109, 0 ≤ a, b < N) 또, 첫 사람이 술을 마시기 위해 필요한 단계의 수는 106보다 작다. 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 술을 마시지 않고 집으로 가는 사람의 수를 출력한다.

예제 입력

2 1 1
5 1 1
10 3 7
101 9 2
698253463 1 181945480
1000000000 999999999 999999999
0

예제 출력

0
2
4
96
698177783
999999994

힌트

조세퍼스 문제는 1158번을 참고하면 된다.