Wolf Trails
In the wild Jungle, alongside the Seeonee wolf pack, there are numerous 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 prevent 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 guidelines are as follows:
Each Council Rock must be located at the center of a square.
There should be exactly one simple path between each pair of 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 Rocks if the distance between them does not exceed k.
If there are more than 10^6 shortest trail options between two Rocks, it is assumed that there are exactly 10^6 trails between them.
There must be exactly one non-intersecting path between each pair of Rocks along the established trails.
Write a program to calculate the number of different ways to lay trails between the Council Rocks.
Input
The first line contains two numbers: n (1 ≤ n ≤ 80) and k (0 ≤ k ≤ 10^18)—the number of Council Rocks and the maximum allowable trail length. The following n lines provide the coordinates of the Council Rocks (all coordinates range from 0 to 10^18).
Output
Output the number of different ways to lay trails between the Council Rocks.