Problem Statement 
 There is a NxN maze where each cell contains either a wall or empty space. You are currently in the topleft cell at coordinates (0, 0) and your goal is to reach the bottomright cell at coordinates (N1, N1) making as few turns as possible. You can choose any of the four cardinal directions as your starting direction. Then, from each cell, you can either move forward one cell in your current direction or turn left or right by 90 degrees. You can only walk into empty cells, not walls.
You are given ints M, X0, Y0, A, B, C and D. Generate lists X and Y, each of length M, using the following recursive definitions:
X[0] = X0 MOD P
X[i] = (X[i1]*A+B) MOD P (note that X[i1]*A+B may overflow a 32bit integer)
Y[0] = Y0 MOD P
Y[i] = (Y[i1]*C+D) MOD P (note that Y[i1]*C+D may overflow a 32bit integer)
Cell (x, y) of the maze contains a wall if and only if it is neither the topleft cell nor the bottomright cell and there exists a value of i between 0 and M1, inclusive, such that x=X[i] MOD N and y=Y[i] MOD N. Return the minimum number of turns you must make to reach the bottomright cell of this maze, or return 1 if it is impossible.


Definition 
 Class:  DoNotTurn  Method:  minimumTurns  Parameters:  int, int, int, int, int, int, int, int, int  Returns:  int  Method signature:  int minimumTurns(int N, int X0, int A, int B, int Y0, int C, int D, int P, int M)  (be sure your method is public) 




Notes 
  In the statement, "A MOD B" represents the remainder of integer division of A by B. For example, 14 MOD 5 = 4 and 20 MOD 4 = 0. 
  The author's solution does not depend on any properties of the pseudorandom generator. It would solve any input of allowed size within the given limits. 

Constraints 
  N will be between 2 and 500, inclusive.

  M will be between 0 and 1,000,000, inclusive.

  X0, Y0, A, B, C and D will each be between 0 and 1,000,000, inclusive.

  P will be between 1 and 1,000,000, inclusive. 

Examples 
0)  
  Returns: 1  There are no walls, so you will have to make only one turn. 


1)  
  Returns: 1  The maze in this case looks as follows ('#' denotes a wall, '.' denotes an empty cell):
.#.
.#.
.#.
The target is unreachable. 


2)  
  Returns: 3  The maze in this case looks as follows ('#' denotes a wall, '.' denotes an empty cell):
.#.
..#
#..
There is only one possible path and it requires 3 turns. 


3)  
 10  911111  845499  866249  688029  742197  312197  384409  40 
 Returns: 12  The maze and the optimal path in it are given below ('#' denotes a wall, '.' denotes an empty cell, the path is illustrated using 'p' characters):
pp##..#..#
#pp..###..
.#p#.....#
##p...#.#.
.#p.##.#..
##p##.#...
#pp####...
pp#.#...#.
p#pppp#...
ppp##ppppp



4)  
  Returns: 2  The maze in this case looks as follows ('#' denotes a wall, '.' denotes an empty cell):
...#.
.....
...#.
.....
..#..



5)  
 