I. Числа или фейерверки
ограничение по времени на тест
12 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Теперь, когда все подарки доставлены, Северный полюс наконец-то в мире — и пришло время отпраздновать это зрелищным новогодним фейерверком!

Северный полюс можно представить как декартову плоскость, на которой расположены $$$n$$$ городов в различных целочисленных точках. Вам также дано целое число $$$k$$$.

Для собственного$$$^{\text{∗}}$$$ подмножества $$$T$$$ городов ($$$T$$$ может быть пустым) мы определяем его зрелищность следующим образом:

  1. Фейерверк запускается из каждого города в $$$T$$$.
  2. Для каждого не входящего в $$$T$$$ города $$$c$$$ определим $$$f$$$ как количество фейерверков, запущенных из городов, которые находятся на расстоянии ровно $$$\sqrt{k}$$$ по евклидовой метрике$$$^{\text{†}}$$$ от $$$c$$$. Присвойте городу $$$c$$$ число $$$(f+1)$$$.
  3. Зрелищность $$$T$$$ равна произведению всех чисел, присвоенных на шаге 2.

Вычислите сумму зрелищностей $$$T$$$ по всем $$$2^n-1$$$ собственным подмножествам $$$T$$$ городов. Поскольку ответ может быть большим, выведите его по модулю $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$Собственным называется любое подмножество, не равное всему множеству.

$$$^{\text{†}}$$$Евклидово расстояние между двумя точками $$$(x, y)$$$ и $$$(p, q)$$$ определяется как $$$\sqrt{(x - p)^2 + (y - q)^2}$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2\le n\le 31$$$, $$$1\leq k \leq2\cdot 10^4$$$).

Затем следуют $$$n$$$ строк, в $$$i$$$-й строке содержатся два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1\leq x_i, y_i\leq 100$$$) — $$$x$$$ и $$$y$$$ координаты $$$i$$$-го города соответственно. Гарантируется, что координаты городов различны.

Гарантируется, что сумма значений $$$n^3$$$ по всем наборам входных данных не превосходит $$$31^3$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — сумму зрелищностей по всем собственным подмножествам $$$T$$$ городов, по модулю $$$998\,244\,353$$$.

Пример
Входные данные
4
3 1
1 2
2 1
2 2
2 20000
1 1
100 100
9 5
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
13 25
50 50
55 50
54 53
53 54
50 55
47 54
46 53
45 50
46 47
47 46
50 45
53 46
54 47
Выходные данные
16
3
8255
560112
Примечание

В первом наборе входных данных приведены $$$2^3-1=7$$$ возможных размещений фейерверков. Числа, присвоенные городам, не входящим в $$$T$$$, обведены в круг.

Общая зрелищность равна $$$(1\cdot 1\cdot 1)+(1\cdot 2)+(2\cdot 1)+(2\cdot 2)+(3)+(2)+(2)=16$$$.

Во втором наборе входных данных есть $$$2^2-1=3$$$ возможных размещения фейерверков. Для каждого размещения, поскольку $$$(1,1)$$$ и $$$(100,100)$$$ имеют евклидово расстояние $$$\sqrt{(100-1)^2+(100-1)^2}=\sqrt{19\,602}\neq\sqrt{20\,000}$$$, ни один из городов не будет иметь фейерверков, находящихся ровно на расстоянии $$$\sqrt{k}$$$. Таким образом, число $$$1$$$ присваивается каждому городу без фейерверков. Следовательно, зрелищность равна $$$1$$$ для каждого $$$T$$$, и ответ равен $$$1+1+1=3$$$.