Solving Modular Hyper-Operator Equation

Hu Yin wants Cirno to solve for (x) in the following equation: [ a \uparrow^n x \equiv b \pmod{p} ] where (a), (n), (b), and (p) are given constants, and (x) is the unknown. Here, Knuth's up-arrow notation is used. For the base case (n = 1), the expression is defined as (a^x). For (n > 1), the expression is defined recursively as follows: [ a \uparrow^n 0 = 1,\quad a \uparrow^n x = a \uparrow^{n-1} \Bigl(a \uparrow^n (x-1)\Bigr) \quad (x \ge 1). ] Your task is to find the smallest non-negative integer (x) such that the equation holds (when evaluated modulo (p)). If no such (x) exists within the search bound, output (-1).

inputFormat

The input consists of four space-separated integers: (a), (n), (b), and (p).

outputFormat

Output the smallest non-negative integer (x) that satisfies the equation modulo (p). If no solution is found within the search limit, output (-1).

sample

2 2 4 5

2