미로 속 보석

스크루지 맥덕은 자신의 재산을 늘릴 새로운 계획을 세웠다. 그는 특별한 미로가 있는 고대 유적을 발견했다. 이 미로는 번호가 0부터 n-1까지 붙은 n개의 방으로 이루어진다. 각 방에는 보석이 정확히 하나씩 있다. 방들은 단방향 터널로 연결되어 있다. 각 방에서 나가는 터널은 정확히 두 개이다. 하나는 번호가 $(a \cdot v^2 + b \cdot v + c) \bmod n$인 방으로 이어지고, 다른 하나는 미로 밖으로 이어진다.

미로의 어느 방에서든 들어가서 터널을 따라 이동하며 보석을 모을 수 있다. 미로 밖으로 나가는 순간 자폭 장치가 작동하여 천장이 무너지고, 가져가지 못한 보석은 모두 영원히 사라진다.

스크루지는 이 미로에서 가져갈 수 있는 보석의 최대 개수를 알고 싶어 한다.

입력의 첫 줄에 이 미로를 정하는 정수 네 개 $a$, $b$, $c$, $n$이 주어진다.

미로에서 가져갈 수 있는 보석의 최대 개수를 나타내는 정수 하나를 한 줄에 출력한다.

시작하는 방에 따라 결과가 달라진다. 예를 들어 첫 번째 테스트 케이스에서 스크루지가 0번 방에서 시작하면, 선택지는 0번 방으로 돌아가는 터널과 밖으로 나가는 터널뿐이라 고를 것이 거의 없다. 2번 방에서 시작해 $2 \rightarrow 8 \rightarrow 16 \rightarrow 32 \rightarrow 0 \rightarrow$ 밖 순서로 따라가는 것이 훨씬 낫다.