Берляндский лес был высажен несколько десятилетий назад в форме бесконечной сетки с деревом в каждой ячейке. Теперь деревья выросли, и они образуют довольно плотную структуру.
Такую плотную, на самом деле, что пожар стал реальной опасностью для леса. Это лето выдалось необычно жарким в Берляндии, и некоторые деревья загорелись!
Секунда, в которую начался пожар, считается секундой \(0\). Каждую секунду пожар захватывал все соседние неповрежденные деревья ко всем горящим на данный момент деревьям. Дерево считается соседним, если оно находится в соседней по стороне или по углу ячейке. К счастью, после \(t\) секунд работники Берлянского пожарного отделения добрались до пожара и мгновенно потушили его.
Теперь они хотят высчитать разрушительную мощь пожара. Пусть \(val_{x, y}\) будет секундой, в которую дерево в ячейке \((x, y)\) загорелось. Разрушительная мощь — это сумма \(val_{x, y}\) по всем \((x, y)\) сгоревших деревьев.
Разумеется, все работники пожарного отделения — пожарные, а не программисты, поэтому они просят Вас помочь им с вычислением разрушительной мощи пожара.
Ответ может быть довольно большим, потому выведите его по модулю \(998244353\).
Выходные данные
Выведите единственное целое число — сумма \(val_{x, y}\) по всем \((x, y)\) сгоревших деревьев по модулю \(998244353\).
Примечание
Здесь представлена визуализация первых трех примеров. Серые клетки имеют \(val = 0\), оранжевые — \(val = 1\) и красные — \(val = 2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 2
10 11
|
40
|
|
2
|
4 1
2 2
1 3
0 2
2 4
|
18
|
|
3
|
3 0
0 0
-2 1
1 1
|
0
|