Wolf Trails#1412
In the wild Jungle, alongside the Seeonee wolf pack, there are many other tribes of the Free People. Each pack has its own traditions, leader, and Council Rock. The Jungle is divided into equal squares, with each tribe assigned specific squares for hunting. Occasionally, wolves from one pack may attend the council of another pack.
To avoid conflicts when entering another pack's territory, the council of elders, made up of pack leaders, decided to establish safe paths between Council Rocks. Their decision is as follows:
Each Council Rock must be located at the center of a square.
There must be exactly one simple path between each pair of Council Rocks, consisting of one or more trails.
The trail must be the shortest possible, made up of segments connecting the centers of adjacent squares along their edges.
A trail can be established between two Council Rocks if the distance between them does not exceed .
If there are more than 10^6 shortest trail options between two Council Rocks, it is assumed that there are exactly 10^6 trails between them.
Between each pair of Council Rocks, there must be exactly one non-intersecting path along the established trails.
Write a program to calculate the number of different ways to lay trails between the Council Rocks.
The first line contains two numbers: (1 \le n \le 80) and (0 \le k \le 10^{18}) — the number of Council Rocks and the maximum allowable trail length. The following lines contain the coordinates of the Council Rocks (all coordinates are between and 10^{18}).
Output the number of different ways to lay trails between the Council Rocks.
Example 1