Canavar yolları
Vəhşi Cəngəlliklərdə, Sioniy canavar sürüsündən başqa, Azad Xalqın bir çox tayfaları da mövcuddur. Hər bir sürünün öz adətləri, başçısı və Məsləhət Daşı var. Cəngəlliklərin ərazisi bərabər kvadratlara bölünüb və hər bir Azad Xalq tayfasına ov edə biləcəkləri kvadratlar ayrılıb. Bəzən, bir sürünün canavarları başqa bir sürünün məsləhətinə gedə bilər.
Münaqişələrin qarşısını almaq üçün sürü başçılarından ibarət ağsaqqallar məclisi, bir Məsləhət Daşından digərinə təhlükəsiz yollar təyin etməyə qərar verdi. Ağsaqqalların qərarı belədir:
Məsləhət Daşı yalnız kvadratın mərkəzində yerləşdirilməlidir;
hər iki Məsləhət Daşı arasında bir və yalnız bir sadə yol olmalıdır ki, bu da bir və ya bir neçə cığırdan ibarət olsun;
çəkilmiş cığır ən qısa uzunluğa malik olmalı və qonşu kvadratların mərkəzlərini birləşdirən seqmentlərdən ibarət olmalıdır;
iki Məsləhət Daşı arasında cığır çəkmək olar, əgər bu iki Məsləhət Daşı arasındakı məsafə k-dan böyük deyilsə;
əgər iki Məsləhət Daşı arasında ən qısa cığırın 10^6-dan çox variantı varsa, bu iki Məsləhət Daşı arasında dəqiq 10^6 cığır olduğunu hesab edirik.
Hər iki Məsləhət Daşı arasında çəkilmiş cığırlar üzrə öz-özünə kəsişməyən bir və yalnız bir yol olmalıdır.
Məsləhət Daşları arasında cığır çəkmək üçün neçə fərqli variantın olduğunu hesablayan bir proqram yazın.
Giriş verilənləri
Birinci sətirdə iki ədəd n (1 ≤ n ≤ 80) və k (0 ≤ k ≤ 10^18) - Məsləhət Daşlarının sayı və cığırın maksimal icazə verilən uzunluğu qeyd olunub. Növbəti n sətir Məsləhət Daşlarının koordinatlarını ehtiva edir (bütün koordinatlar 0 ilə 10^18 arasında yerləşir).
Çıxış verilənləri
Məsləhət Daşları arasında cığır çəkmək üçün neçə fərqli variantın olduğunu göstərin.