Recurrence and Period

Time limit0.5sMemory limit512 MB

Summary

Given a prime p and the recurrence x_n = a*x_{n-1} + b*x_{n-2} mod p, find the lexicographically smallest (S, T) where the sequence becomes periodic with period T from index S.

Level: Hard8 of 10
Topics: Number theory, Matrix, Math
Solved: No attempts yet

Problem

Given a prime $p$ , the recurrence $x_n = ax_{n-1} + bx_{n-2}$ ( $n \ge 2$ ), and the initial terms $x_0$ and $x_1$ , the pigeonhole principle guarantees the existence of integers $S \ge 0$ and $T > 0$ that satisfy the following condition.

Condition: for every integer $n \ge S$ , $x_{n+T} - x_n$ is a multiple of $p$ .

Find the pair $(S, T)$ that satisfies the condition and is smallest in lexicographic order.

Input

The first line contains integers $p, a, b, x_0, x_1$ . It is guaranteed that $p$ is prime.

Output

Print the pair $(S, T)$ that satisfies the condition and is smallest in lexicographic order on the first line.

Constraints

$0 < p \le 2147483647$
$0 \le a, b, x_0, x_1 < p$

Examples3

Example 1
Input
```
89 1 1 1 1
```
Expected output
```
0 44
```
Example 2
Input
```
1234567891 1 0 794594 353243
```
Expected output
```
1 1
```
Example 3
Input
```
100003 2 100002 7 10
```
Expected output
```
0 100003
```