Problem E: 玩弹簧的PIPI

Problem E: 玩弹簧的PIPI

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 22  Solved: 8
[Submit] [Status] [Web Board] [Creator:]

Description

n个弹簧围成一圈,编号为0,1,...,n-1,第i个弹簧的弹力为a_i,当PIPI站在第i个弹簧时,PIPI可以被弹到[i-a_i,i+a_i]的任意一个位置(注意位置0与位置n-1相邻,即可以把位置-1,-2,...看作位置n-1,n-2,...,位置n,n+1,...看作位置0,1,...
PIPI现在站在位置s,请问PIPI至少需要被弹几次才能到达位置t如果不能到达输出-1

Input

第一行3个整数n,s,t(1\le n\le 10^7,0\le s,t<n)
第二行4个整数a_0,g,seed,p(0\le a_0,g,seed<p,1\le p\le n)
对于1\le i<na_i=(a_{i-1}*g+seed)\bmod p

Output

输出一行一个整数表示答案。

Sample Input

9 0 2 
1 3 4 7

Sample Output

2

HINT

经过递推计算后a_0,a_1,...,a_81,0,4,2,3,6,1,0,4
一开始PIPI站在位置0,由于a_0=1,故PIPI可以被弹到位置8,0,1
如果PIPI被弹到位置1,由于a_1=0PIPI就不能再移动了。
如果PIPI被弹到位置8,由于a_8=4,故PIPI可以被弹到位置4,5,6,7,8,0,1,2,3PIPI接下来直接被弹到位置2即可。
因此最少需要被弹2次。