← 返回题目列表

Codeforces · 547/A

A. 迈克和青蛙

中文机器翻译题面 查看原题

迈克有一只青蛙和一朵花。他的青蛙名叫 Xaniar,他的花名叫 Abol。最初(在时间 0),Xaniar 的高度为 h1,Abol 的高度为 h2。迈克每一秒都在给阿博尔和夏尼亚尔浇水。

因此,如果 Xaniar 的高度为 h1,Abol 的高度为 h2,一秒后 Xaniar 的高度将变为 $$( x _ { 1 } h _ { 1 } + y _ { 1 } ) \bmod m$$,Abol 的高度将变为 $$( x _ { 2 } h _ { 2 } + y _ { 2 } ) \bmod m$$ 其中 x1、y1、x2 和 y2 是一些整数,$$a \bmod b$$ 表示 a 模 b 的余数。

Mike 是一位竞技程序员迷。他想知道 Xania 的高度为 a1、Abol 的高度为 a2 所需的最短时间。

迈克请求您提供帮助。计算最短时间或说它永远不会发生。

输入

输入的第一行包含整数 m (2 ≤ m ≤ 106)。

输入的第二行包含整数 h1 和 a1 (0 ≤ h1, a1 < m)。

输入的第三行包含整数 x1 和 y1 (0 ≤ x1, y1 < m)。

输入的第四行包含整数 h2 和 a2 (0 ≤ h2, a2 < m)。

输入的第五行包含整数 x2 和 y2 (0 ≤ x2, y2 < m)。

保证 h1 ≠ a1 且 h2 ≠ a2。

输出

打印 Xaniar 达到高度 a1 并且 Abol 达到高度 a2 之前的最小秒数,否则打印 -1。

示例

输入 #1

5
4 2
1 1
0 1
2 3

输出 #1

3

输入 #2

1023
1 2
1 0
1 2
1 1

输出 #2

-1

注意

在第一个示例中,高度序列如下:

Xaniar:$$4 \rightarrow 0 \rightarrow 1 \rightarrow 2$$

Abol: $$0 \rightarrow 3 \rightarrow 4 \rightarrow 1$$