Mike and Frog

## 题目描述 迈克有一只青蛙和一朵花，它的青蛙叫Xaniar，花叫Abol。 开始（时间为0），它的青蛙高度为 $ h_{1}$,花高度为$ h_{2}$。每一秒，迈克都会给他们两个浇水，因此每过一秒青蛙的高度都会由当前的$ h_{1}$变为$(x_{1}\times h_{1}+ y_{1}) mod\ m$,同理，花的高度都会由当前的$ h_{2}$变为$(x_{2}\times h_{2}+ y_{2}) mod\ m$。 已知$x_{1},y_{1},x_{2},y_{2}$都是整数，并且$a\ mod\ b$表示$a$除以$b$所得的余数。 迈克想知道最少多久后青蛙的高度会变成$a_{1}$ 花的高度会变成$a_{2}$。请你计算出最短时间或者告诉迈克这件事根本不会发生。 ## 输入格式 第一行一个整数$m$，$(2<=m<=10^{6})$ 第二行包含两个整数 $h_{1}$ 和$a_{1}$($0<=h_{1},a_{1}<=m$ ) 第三行包含两个整数 $x_{1}$ 和$y_{1}$($0<=x_{1},y_{1}<=m$ ) 第四行包含两个整数 $h_{2}$ 和$a_{2}$($0<=h_{2},a_{2}<=m$ ) 第五行包含两个整数 $x_{2}$ 和$y_{2}$($0<=x_{2},y_{2}<=m$ ) 输入数据保证$h_{1}≠a_{1}$ 并且 $h_{2}≠a_{2}$ ## 输出格式 如果能实现，输出最短时间；否则，输出-1即可。

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_{1} $ and height of Abol is $ h_{2} $ . Each second, Mike waters Abol and Xaniar. So, if height of Xaniar is $ h_{1} $ and height of Abol is $ h_{2} $ , after one second height of Xaniar will become  and height of Abol will become  where $ x_{1},y_{1},x_{2} $ and $ y_{2} $ 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_{1} $ and height of Abol is $ a_{2} $ . 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^{6} $ ). The second line of input contains integers $ h_{1} $ and $ a_{1} $ ( $ 0<=h_{1},a_{1}&lt;m $ ). The third line of input contains integers $ x_{1} $ and $ y_{1} $ ( $ 0<=x_{1},y_{1}&lt;m $ ). The fourth line of input contains integers $ h_{2} $ and $ a_{2} $ ( $ 0<=h_{2},a_{2}&lt;m $ ). The fifth line of input contains integers $ x_{2} $ and $ y_{2} $ ( $ 0<=x_{2},y_{2}&lt;m $ ). It is guaranteed that $ h_{1}≠a_{1} $ and $ h_{2}≠a_{2} $ .

Print the minimum number of seconds until Xaniar reaches height $ a_{1} $ and Abol reaches height $ a_{2} $ or print -1 otherwise.

5
4 2
1 1
0 1
2 3

3

1023
1 2
1 0
1 2
1 1

-1

In the first sample, heights sequences are following: Xaniar:  Abol: