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.

样例 #1

样例输入 #1

5
4 2
1 1
0 1
2 3

样例输出 #1

3

样例 #2

样例输入 #2

1023
1 2
1 0
1 2
1 1

样例输出 #2

-1

提示

In the first sample, heights sequences are following:

Xaniar:

Abol: