Many cryptographic keys make use of so-called generators. This is for example the case for the Diffie-Hellman key exchange¹ protocol. We say that the number $$g \in \mathbb{N}_0$$ is a generator of the prime number $$p \in \mathbb{N}_0$$ (with $$g < p$$) if the smallest number $$n \in \mathbb{N}$$ (with $$n > 1$$) such that $$g^n\ \text{mod}\ p \equiv g$$ is equal to $$p$$. The modulo operator $$\text{mod}$$ finds the remainder after (integer) division.

Suppose that $$g = 5$$ and $$p = 7$$. We then compute the successive powers of $$g = 5$$, starting with the second power, each time computing the remainder after division by the prime number $$p = 7$$. \[ \begin{array}{rcl} 5^2 \mod 7 &=& 4 \\ 5^3 \mod 7 &=& 6 \\ 5^4 \mod 7 &=& 2 \\ 5^5 \mod 7 &=& 3 \\ 5^6 \mod 7 &=& 1 \\ 5^7 \mod 7 &=& 5 \end{array} \] This process will always yield a result that equals $$g = 5$$ for a certain power (a property of prime numbers), which in this case happens for the first time with the seventh power. Because 7 is also the value of the prime number $$p$$, we say that $$g = 5$$ is a generator of $$p = 7$$.

Suppose that $$g = 4$$ and $$p = 7$$. We again compute the successive powers of $$g = 4$$, starting with the second power, until the process results in the number $$g = 4$$. \[ \begin{array}{rcl} 4^2 \mod 7 &=& 2 \\ 4^3 \mod 7 &=& 1 \\ 4^4 \mod 7 &=& 4 \end{array} \] Because this happens for the first time with the fourth power, and 4 is not equal to the prime number $$p$$, we say that $$g = 4$$ is not a generator of $$p = 7$$.

Input

Two numbers $$g, p \in \mathbb{N}_0$$, each on a separate line. The value $$p$$ is a prime number, with $$g < p$$.

Output

Determine whether the number $$g$$ is a generator of the number $$p$$. You do this by computing the successive powers of $$g$$, starting with the second power, and finding the remainder after division by the number $$p$$. Do this until you obtain the number $$g$$ for the first time (this will always happen because $$p$$ is a prime number). For each power evaluated, a single line of output must be generated whose format and content can be derived from the examples given below (we represent $$m^n$$ as m^n).

After all powers have been evaluated and the corresponding lines of output have been generated, a last line of output must be generated that indicates whether $$g$$ is a generator of $$p$$. Again, you can derive the format of this line from the examples given below.

Example

Input:

5
7

Output:

(5^2) mod 7 = 4
(5^3) mod 7 = 6
(5^4) mod 7 = 2
(5^5) mod 7 = 3
(5^6) mod 7 = 1
(5^7) mod 7 = 5
5 is a generator of 7

Example

Input:

4
7

Output:

(4^2) mod 7 = 2
(4^3) mod 7 = 1
(4^4) mod 7 = 4
4 is not a generator of 7