Mike has a frog and a flower. His frog is named Xaniar and his flower is named Abol. Initially(at time 0), height of Xaniar is h₁ and height of Abol is h₂. Each second, Mike waters Abol and Xaniar.

$\text{[math]}$

So, if height of Xaniar is h₁ and height of Abol is h₂, after one second height of Xaniar will become $\text{[math]}$ and height of Abol will become $\text{[math]}$ where x₁, y₁, x₂ and y₂ are some integer numbers and $\text{[math]}$ denotes the remainder of a modulo b.

Mike is a competitive programmer fan. He wants to know the minimum time it takes until height of Xania is a₁ and height of Abol is a₂.

Mike has asked you for your help. Calculate the minimum time or say it will never happen.

Input

The first line of input contains integer m (2 ≤ m ≤ 10⁶).

The second line of input contains integers h₁ and a₁ (0 ≤ h₁, a₁ < m).

The third line of input contains integers x₁ and y₁ (0 ≤ x₁, y₁ < m).

The fourth line of input contains integers h₂ and a₂ (0 ≤ h₂, a₂ < m).

The fifth line of input contains integers x₂ and y₂ (0 ≤ x₂, y₂ < m).

It is guaranteed that h₁ ≠ a₁ and h₂ ≠ a₂.

Output

Print the minimum number of seconds until Xaniar reaches height a₁ and Abol reaches height a₂ or print -1 otherwise.

Note

In the first sample, heights sequences are following:

Xaniar: $\text{[math]}$

Abol: $\text{[math]}$

Mike and Frog

Examples