Перед торговым центром расположилась замечательная аллея с деревьями. Как жаль, что придется от нее избавиться, чтобы освободить место под парковку...
Деревья на аллее растут в один ряд. Есть \(n\) мест под деревья: позиция \(0\) — это торговый центр, позиция \(n+1\) — это дорога, а позиции с \(1\) по \(n\) — это места под деревья. Некоторые из них заняты — в них растут деревья одинаковой высоты \(k\). Не более одного дерева растет на каждом месте.
Когда вы срубаете дерево на месте \(x\), то вы можете его свалить либо налево, либо направо. Если оно падает налево, то занимает места с \(x-k\) по \(x\) включительно. Если оно падает направо, то занимает места с \(x\) по \(x+k\) включительно.
Пусть \(m\) деревьев растут на аллее в каких-то местах \(x_1, x_2, \dots, x_m\). Назовем аллею неудачной, если все \(m\) деревьев можно срубить таким образом, чтобы:
- ни одно дерево не упало на торговый центр или дорогу;
- ни одно место не было занято более чем одним упавшим деревом.
Посчитайте количество различных неудачных аллей с \(m\) деревьями высоты \(k\). Две аллеи считаются различными, если есть такое место \(y\), что дерево растет на месте \(y\) на первой аллее и не растет на месте \(y\) на второй аллее.
Выведите это число по модулю \(998\,244\,353\).
Выходные данные
Выведите одно целое число — количество различных неудачных аллей с \(m\) деревьями высоты \(k\) по модулю \(998\,244\,353\).