Вовчі стежки#1412
У дикій Джунглі, поруч із зграєю вовків із Сіоні, є багато інших племен Вільних Людей. Кожна зграя має свої традиції, лідера й Раду-Скелю. Джунглі поділені на рівні квадрати, кожному племені виділено певні квадрати для полювання. Іноді вовки з однієї зграї можуть відвідувати раду іншої зграї.
Щоб уникнути конфліктів при вході на територію іншої зграї, рада старійшин, що складається з ватажків зграї, вирішила прокласти безпечні стежки між Радами-Скелями. Їхнє рішення таке:
Кожна Рада-Скеля має бути розташована в центрі квадрата.
Між кожною парою Рад-Скель має бути рівно один простий шлях, що складається з однієї або кількох стежок.
Стежка повинна бути найкоротшою можливою, складатися із відрізків, що з'єднують центри сусідніх квадратів по їхніх ребрах.
Стежку можна прокласти між двома Радами-Скелями, якщо відстань між ними не перевищує .
Якщо між двома Радами-Скелями існує більше 10^6 варіантів найкоротших стежок, вважається, що між ними рівно 10^6 стежок.
Між кожною парою Рад-Скель повинен бути рівно один неперетинний шлях уздовж прокладених стежок.
Напишіть програму, яка обчислить кількість різних способів прокласти стежки між Радами-Скелями.
Перший рядок містить два числа: (1 \le n \le 80) та (0 \le k \le 10^{18}) — кількість Рад-Скель і максимально допустима довжина стежки. Наступні рядків містять координати Рад-Скель (усі координати між та 10^{18}).
Виведіть кількість різних способів прокласти стежки між Радами-Скелями.
Приклад 1