점화식과 주기

소수 $p$ 와 점화식 $x\_n = ax\_{n-1} + bx\_{n-2} (n \ge 2)$ , 그리고 초항 $x\_0$ , $x\_1$ 이 정해지면, 다음 조건을 만족하는 정수 $S \ge 0, T > 0$ 의 존재는 비둘기집의 원리에 의해 보장된다.

조건: 모든 $S$ 이상의 정수 $n$ 에 대해 $x\_{n+T} - x\_{n}$ 가 $p$ 의 배수

문제는 위 조건을 만족하는 $(S,T)$ 중 사전순으로 가장 작은 것을 찾는 것이다.

첫째 줄에 정수 $p, a, b, x\_0, x\_1$ 가 주어진다. $p$ 는 소수임이 보장된다.

첫째 줄에 조건을 만족하는 $(S, T)$ 중 사전순으로 가장 작은 것을 출력한다.