迈克有一只青蛙和一朵花。他的青蛙名叫 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$$