Congruence Equation

정수 x가 주어진다. 양의 정수 n (1 ≤ n ≤ x) 중 $n ⋅ a^n ≡ b (mod\;p), where a, b, p$을 만족하는 것이 몇 개인지 알아내는 것이 과제이다. 이들은 모두 알려진 상수이다.

유일한 줄에 네 정수 a,b,p,x (2 ≤ p ≤ $10^6$+3, 1 ≤ a,b < p, 1 ≤ x ≤ $10^{12}$)가 주어진다. p이 소수임이 보장된다.

가능한 답 n의 개수를 나타내는 단일 정수를 출력한다.

첫 번째 예제에서는 n=2와 n=8이 가능한 답임을 알 수 있다.