Consider the following recurrence relation: A[i] = ( A[i-1] * x + y ) mod z
where A[0] , x , y and z are given values.
There's a circular plaza with n coffee shops numbered sequentially from 0 to n-1 (evenly spaced 1 unit apart) located along its circumference. From any shop i , you can jump up to A[i] units along the plaza's circumference in either the clockwise or counterclockwise direction. For example, if A[i]=2 , you can jump to any position in { i-2 , i-1 , i , i+1 , i+2 }.
You'll be standing at point start and your friend is at point end. Assuming a single jump takes 1 second, find the minimum number of seconds it will take you to meet up with your friend for coffee. If it's impossible for you to meet your friend (e.g., if you are stuck in a position where A[i] = 0), print "sad" instead.
Note: If you and your friend start out at the same location, you meet with your friend in 0 seconds.
Input Format
The first line contains three space-separated integers describing the respective values of n , start and end. The second line contains four space-separated integers describing the respective values of A[0] , x , y and z.
Constraints
- 1 <= n <= 10^7
- 0 <= start , end < n
- 1 <= z <= n
- 0 <= A[0] , x , y < z
Output Format
Print the minimum number of seconds you'll take to meet up with your friend. If you're unable to meet up , print "sad" instead.
Explanation
Given A[0] , x , y and z we calculate the following maximum distances that you can jump to from each position :
A[0] = 1
A[1] = ( 1 * 3 + 4 ) mod 7 = 0
A[2] = ( 0 * 3 + 4 ) mod 7 = 4
A[3] = ( 4 * 3 + 4 ) mod 7 = 2
A[4] = ( 2 * 3 + 4 ) mod 7 = 3
A[5] = ( 3 * 3 + 4 ) mod 7 = 6
A[6] = ( 6 * 3 + 4 ) mod 7 = 1
A[7] = ( 1 * 3 + 4 ) mod 7 = 0
A[8] = ( 0 * 3 + 4 ) mod 7 = 4
You can meet your friend by performing the following sequence of actions:
-
During the first second, you can jump up to A[0] = 1 units from point 0 to another point ie. jump 1 unit in the counterclockwise direction from point 0 to point 8.
-
During the second second, you can jump up to A[8] = 4 units from point 8 to another point ie. jump 3 units in the clockwise direction from point 8 to point 2 where your friend is waiting.
Because it took two seconds to reach your friend, print 2 as the answer.
