Field modulo — Eolymp

Input

Five integers $a, b, c, n, p$ a, b, c, n, p are given. It is known that:

Print two integers $x$ and $y$ — the coefficients of $1$ and $c$ \sqrt{c} respectively, modulo $p$ .

In the first example:

(2 + 5 ​)^{2} m o d 17 = 9 + 45

(2 + \sqrt{5})^{2}~ mod~17 = 9 + 4 \sqrt{5}

In the second example:

(3 + 25 ​)^{10} m o d 17 = 5 + 115

(3 + 2 \sqrt{5})^{10}~ mod~17 = 5 + 11 \sqrt{5}

Example 1

Loading

Example 2

Loading

You should work in the extended field:

Z_{p} (c) = {x + y c ∣ x, y \in Z_{p}}

Z_p(\sqrt{c}) = \{ x + y \sqrt{c}~|~x, y \in Z_p \}

Operation rules:

Addition
$(x_{1} + y_{1} c) + (x_{2} + y_{2} c) = (x_{1} + x_{2}) + (y_{1} + y_{2}) c$
(x_1 + y_1 \sqrt{c}) + (x_2 + y_2 \sqrt{c}) = (x_1 + x_2) + (y_1 + y_2) \sqrt{c}
Multiplication
$(x_{1} + y_{1} c) \cdot (x_{2} + y_{2} c) = (x_{1} x_{2} + c y_{1} y_{2}) + (x_{1} y_{2} + x_{2} y_{1}) c$
(x_1 + y_1 \sqrt{c}) \cdot (x_2 + y_2 \sqrt{c}) = (x_1 x_2 + c y_1 y_2) + (x_1 y_2 + x_2 y_1) \sqrt{c}

All operations are performed modulo $p$ .