Given a A x A board, find the probability that a knight placed at (C, D) will remain inside board after B moves. Once the horse leave board it cannot return back. The probablity of choosing any of eight moves is equal.
Note: If probablity is p / q then return (p * q-1) % 100000007. where q-1 is modulo inverse 100000007.
First argument is a integer A denoting size of board. Second argument is a integer B denoting number of moves. Third argument is a integer C denoting X- Coordinate of initial position. Fourth argument is a integer D denoting Y- Coordinate of initial position.
1 <= A <= 200 0 <= B <= 1000 1 <= C,D <= A 1 <= A x A x B <= 10^6
return a single integer denoting probablity of horse inside board.
Input 1: A = 5 , B = 1 , C = 5 , D = 5 Output 1: 25000002 Explanation 1: There are only 2 positions inside the board after 1 move so probablity is 2/8 or 1/4 Input 2: A = 10 , B = 2 , C = 1 , D = 1 Output 2: 68750005
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.