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

**Input Format:**

```
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.
```

**Constraints:**

```
1 <= A <= 200
0 <= B <= 1000
1 <= C,D <= A
1 <= A x A x B <= 10^6
```

**Output Format:**

```
return a single integer denoting probablity of horse inside board.
```

**For Example:**

```
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.

Sign Up

to access hints and editorial solutions for**Probablity of knight inside chess board**

to access hints and editorial solutions for

Loading...