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.

So, if height of Xaniar is h₁ and height of Abol is h₂, after one second height of Xaniar will become and height of Abol will become where x₁,y₁,x₂ and y₂ are some integer numbers and 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.

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₂.

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