Avoiding the Heat

Time limit1sMemory limit512 MB

Summary

Count the lattice paths from a start point to a home point using at most T unit steps in the four cardinal directions, avoiding N blocked points.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics, Prefix sum, Math
Solved: No attempts yet

Problem

"Today's high in Seoul is expected to reach 38 degrees Celsius. A heat wave warning is in effect nationwide, and..."

Seongwon regrets going outside today instead of lying at home in front of the air conditioner. He is lost. Surrounded by buildings and signs he has never seen before, he begins to feel his life is in danger. If he fails to reach home and $T$ seconds pass, he will collapse from the heat. Outside the blanket really is dangerous.

Feeling his life is in danger, Seongwon is heading somewhere, anywhere, to get home. He can walk 1 meter per second in one of the four cardinal directions. If he keeps walking in any direction like this, might he reach home eventually?

Seunghyeon, who has been watching the lost Seongwon from home, decides to go rescue him if he truly collapses from the heat. Seunghyeon knows the map and Seongwon's current position, and knows where the buildings are that block movement. Seunghyeon wants to know the number of ways Seongwon can reach home safely. But since Seunghyeon must make full preparations to go out and rescue Seongwon in the sweltering weather, he asks you to do the calculation.

Given Seongwon's current position, the time he can endure the heat, the position of his home, and the number and positions of the obstacles, count the number of ways Seongwon can reach home within $T$ seconds. If the arrival time is the same but the route taken differs, they count as different ways. Seongwon can change direction every second (if he feels this is not the way, he can turn back the way he came), and he cannot step on a point with an obstacle. Once Seongwon reaches home, he stops moving and never goes outside again.

Input

The first line gives two integers representing Seongwon's current position $(X_s, Y_s)$ . The second line gives the time $T(1 \le T \le 200)$ that Seongwon can endure the heat. The third line gives two integers representing the position of his home $(X_h, Y_h)$ .

The fourth line gives the number of obstacles $N(0 \le N \le 100,000)$ . The following $N$ lines each give two integers representing the position of an obstacle $(X_i, Y_i)$ .

All coordinates given are integers between -100,000 and 100,000 inclusive, in meters. All coordinate positions given are distinct.

Output

On the first line, print the number of ways Seongwon reaches home within $T$ seconds, modulo $10^9+7$ .

Examples2

Example 1
Input
```
1 2
4
0 0
1
0 2
```
Expected output
```
2
```
Example 2
Input
```
1 2
4
0 0
2
0 2
1 1
```
Expected output
```
0
```