Sum in field — 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:

i = 0 \sum 2 (2 + 5 ​)^{i} m o d 17 = (1 + (2 + 5) + (9 + 45)) m o d 17 = 12 + 55

\sum_{i = 0}^2 (2 + \sqrt{5})^i~mod~17 = (1 + (2 + \sqrt{5}) + (9 + 4 \sqrt{5}))~mod~17 = 12 + 5 \sqrt{5}

In the second example:

i = 0 \sum 10 (3 + 25 ​)^{i} m o d 17 = 15 + 65

\sum_{i = 0}^{10} (3 + 2 \sqrt{5})^i~ mod~17 = 15 + 6 \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$ .