Problem E
Entertaining Excursion
You have been awarded the prestigious “Employee of the Year Award” at Theatre Software for making a big breakthrough in web technology. In order to show her appreciation for your work, the CEO of Theatre Software has gifted you with a conference trip to Skyhattan City that you always wanted to visit but could not because everything there is too expensive.
Once you have settled at your hotel, you decide to visit the infamous old restaurant at Slump Tower. However, as you leave the hotel doors, you remember that the restaurant does not accept credit cards, which means that you have to go to the bank first in order to withdraw some cash.
You are getting hungry, so you do not want to take a longer route than necessary. But at the same time you want to maximize the touristing part of the trip which means that you absolutely do not want to visit the same place twice. Given these requirements, what is the number of ways that you can reach the Slump Tower?
Assume that Skyhattan’s layout is a square grid which consists of blocks with integer coordinates. A move means going to one of the four (north, south, east, west) adjacent blocks.
Input
The input consists of four lines:
-
The first line of input consists for two integers $W$ and $W$ – the dimensions of Skyhattan in blocks where $2 \leq W, H \leq 100)$.
-
The second line of input consists of two integers $x_{hotel}$ and $y_{hotel}$ – the coordinates of the hotel’s block $(1 \leq x_{hotel} \leq W, 1 \leq y_{hotel} \leq H)$.
-
The third line of input consists of two integers $x_{bank}$ and $y_{bank}$ – the coordinates of the bank’s block $(1 \leq x_{bank} \leq W, 1 \leq y_{bank} \leq H)$.
-
The forth line of input consists of two integers $x_{restaurant}$ and $y_{restaurant}$ – the coordinates of the restaurant’s block $(1 \leq x_{restaurant} \leq W, 1 \leq y_{restaurant} \leq H)$.
Output
Output a single integer – the number of ways to reach the Slump Tower from the hotel via bank with least amount of moves but without visiting the same block more than once. Since the number can be pretty large, output the number in mod $1\, 000\, 000\, 007$.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 3 1 1 3 3 2 2 |
2 |
